考虑到图是\(tag\)，我们依次按拓扑序考虑：
我们发现，如果我们按这个顺序考虑，则会有两个集合\(S,T\)，其中所有跨集合边都是从一个固定集合到另外一个集合的。
我们利用这个性质，对每个点拓扑求出从他出发，和以他结尾的边的最长路径。
那么我们只要按拓扑序依次考虑删掉某个点后的变化，以及这个点加入\(S\)后会给所有路径的操作即可。
用\(multiset\)维护。
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<set>
#include<bits/stdc++.h>
#define ll long long
#define N 500005
std::vector<int>tin[N],tout[N];
ll in[N],out[N];
ll n,m;
ll q[N];
std::queue<int>QWQ;
ll din[N],dout[N];
inline void top_in(){
for(int i = 1;i <= n;++i){
if(!in[i]){
QWQ.push(i);
}
}
while(QWQ.size()){
int u = QWQ.front();
q[++q[0]] = u;
QWQ.pop();
for(int i = 0;i < tout[u].size();++i){
in[tout[u][i]] -- ;
din[tout[u][i]] = std::max(din[tout[u][i]],din[u] + 1);
if(!in[tout[u][i]])
QWQ.push(tout[u][i]);
}
}
}
inline void top_out(){
for(int i = 1;i <= n;++i){
if(!out[i]){
QWQ.push(i);
}
}
while(QWQ.size()){
int u = QWQ.front();
QWQ.pop();
for(int i = 0;i < tin[u].size();++i){
out[tin[u][i]] -- ;
dout[tin[u][i]] = std::max(dout[tin[u][i]],dout[u] + 1);
if(!out[tin[u][i]])
QWQ.push(tin[u][i]);
}
}
}
std::multiset<ll>QAQ;
ll ans = 0;
ll ansk ;
int main(){
scanf("%lld%lld",&n,&m);
for(int i = 1;i <= m;++i){
ll x,y;
scanf("%lld%lld",&x,&y);
tin[y].push_back(x);
tout[x].push_back(y);
in[y] ++ ;
out[x] ++ ;
}
top_in();
top_out();
for(int i = 1;i <= n;++i){
QAQ.insert(dout[i]);
}
ans = *QAQ.rbegin();
for(int i = 1;i <= q[0];++i){
int u = q[i];
QAQ.erase(QAQ.find(dout[u]));
for(int j = 0;j < tin[u].size();++j){
QAQ.erase(QAQ.find((dout[u] + din[tin[u][j]] + 1)));
}
ll tmp = *QAQ.rbegin();
if(tmp < ans)
ans = tmp,ansk = u;
for(int j = 0;j < tout[u].size();++j){
QAQ.insert(din[u] + dout[tout[u][j]] + 1);
}
QAQ.insert(din[u]);
}
std::cout<<ansk<<" "<<ans<<std::endl;
}