非常好题目，爱来自 xc。
-
看到有向无环图，想到拓扑序。通过拓扑序，可以轻松求出以每个点为起点的最长路 \(disS\)与每个点为终点的最长路 \(disF\)。
-
如何求总共的最长路？在 \(disS,disF,disS_u + 1 + disF_v((u,v)\in E)\) 中取最大值即可。注意最后一项，表示将连边的二点值相加。
-
如何处理删点？删掉一个点后，有一些点的 \(disS\) 不会变，有一些点的 \(disT\) 不会变。我们不妨把这两类点进行分组，得到组 \(A\) 和组 \(B\)。
-
为什么要进行分组？因为第三类取值 \(disS_u + 1 + disF_v\) 只会在两组间连边产生，且 \(u\in A,v\in B\)。因为只有此时 \(disS_u\) 和 \(disF_v\) 才不会受删点影响。
-
发现 \(A\) 与 \(B\) 的单次加减是简单的，于是我们考虑递推每一个答案。
-
若当前求的点为 \(u\)，不妨认为在这之后我们会将 \(u\) 从 \(B\) 中加入 \(A\) 中。那么我们要删除 \(disF_u\) 以及所有包含 \(disF_u\) 的第三类值，同时加入 \(disS_u\) 与所有包含 \(disS_u\) 的第三类值。此时最大值就是答案。
-
注意到上述过程需要满足当加入 \(u\) 时，所有 \(u\) 连向的点还在 \(B\) 内。因此递推的顺序是翻转的拓扑序。
-
删除加入求最大值可以用优先队列解决，由于一次就写过了不知道有什么需要注意的点。
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
template<typename T> bool chkmax(T &a, T b) { return a < b ? (a = b, 1) : 0; }
template<typename T> bool chkmin(T &a, T b) { return a > b ? (a = b, 1) : 0; }
int n, m;
namespace Graph {
template<const int M>
struct graph {
int st[M], nx[M << 1], to[M << 1], cnt;
void add(int u, int v) { to[++cnt] = v;nx[cnt] = st[u];st[u] = cnt; }
};
#define go(g, u, v) for (int i = g.st[u], v = g.to[i]; i; i = g.nx[i], v = g.to[i])
graph<N << 1> g, ig;
int in[N], out[N], hisI[N], hisO[N];
bool vis[N];
void add(int u, int v) {
g.add(u, v);
ig.add(v, u);
vis[u] = vis[v] = true;
++hisI[v];++hisO[u];
++in[v];++in[u];
}
void init() {
for (int i = 1; i <= n; ++i) in[i] = hisI[i], out[i] = hisO[i];
}
vector<int> A, B;
int disS[N], disF[N];
void findS() {
init();
queue<int> q;
for (int i = 1; i <= n; ++i) if (out[i] == 0 && vis[i] == true) q.push(i);
while (!q.empty()) {
int u = q.front();q.pop();
A.push_back(u);
go (ig, u, v) {
if (--out[v] == 0) q.push(v);
chkmax(disS[v], disS[u] + 1);
}
}
for (int i = A.size() - 1; i >= 0; --i) B.push_back(A[i]);
}
void findF() {
init();
queue<int> q;
for (int i = 1; i <= n; ++i) if (in[i] == 0) q.push(i);
while (!q.empty()) {
int u = q.front();q.pop();
go (g, u, v) {
if (--in[v] == 0) q.push(v);
chkmax(disF[v], disF[u] + 1);
}
}
}
struct Pqueue {
priority_queue<int> q, del;
void push(int x) { q.push(x); }
void pop(int x) { del.push(x); }
int top() {
while (!del.empty() && q.top() == del.top()) q.pop(), del.pop();
return q.top();
}
int size() {
while (!del.empty() && q.top() == del.top()) q.pop(), del.pop();
return q.size();
}
}Q;
pair<int, int> work() {
int ans = 2147483647, id = 0;
for (int i = 1; i <= n; ++i) Q.push(disS[i]);
for (auto u : B) {
Q.pop(disS[u]);
go (ig, u, v) Q.pop(disF[v] + 1 + disS[u]);
if (chkmin(ans, Q.top())) id = u;
go (g, u, v) Q.push(disF[u] + 1 + disS[v]);
Q.push(disF[u]);
}
return make_pair(id, ans);
}
}
int main() {
freopen("text.in", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n >> m;
for (int i = 1, u, v; i <= m; ++i) {
cin >> u >> v;
Graph::add(u, v);
}
Graph::findS();
Graph::findF();
pair<int, int> ans = Graph::work();
cout << ans.first << ' ' << ans.second << endl;
return 0;
}