f[0][i]为i出发的最长路，f[1][i]为到i的最长路
新建源汇S,T，S向每个点连边，每个点向T连边
将所有点划分为两个集合S与T，一开始S中只有S，其它点都在T中
用一棵线段树维护所有连接属于两个集合的点的边，权值为f[1][u]+f[0][v]
按拓扑序依次计算去掉每个点后图中的最长路
对于当前计算的点x，先将所有连向x的边删除，此时最长路长度为线段树中的最大值
然后再将所有x出发的边加入线段树中
时间复杂度$O(m\log n)$
#include<cstdio>
#define N 500010
int n,m,i,j,x,y,g[2][N],nxt[2][N<<2],v[2][N<<2],ed,d[N],q[N],l,r,fin,ans,f[2][N],S,T,val[N<<2];
inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}
inline void add(int x,int y){
d[x]++;v[0][++ed]=y;nxt[0][ed]=g[0][x];g[0][x]=ed;
v[1][ed]=x;nxt[1][ed]=g[1][y];g[1][y]=ed;
}
inline void ins(int c,int d){
int x=1,a=0,b=n,mid;
while(a<=b){
val[x]+=d;
if(a==b)return;
mid=(a+b)>>1;x<<=1;
if(c<=mid)b=mid;else a=mid+1,x|=1;
}
}
inline int ask(){
int x=1,a=0,b=n,mid;
while(a<b){
mid=(a+b)>>1;x<<=1;
if(val[x|1])a=mid+1,x|=1;else b=mid;
}
return a;
}
int main(){
read(n),read(m);
while(m--)read(x),read(y),add(x,y);
for(i=1;i<=n;i++)if(!d[i])q[++r]=i;
while(l<=r)for(i=g[1][q[l++]];i;i=nxt[1][i])if(!(--d[v[1][i]]))q[++r]=v[1][i];
for(i=1;i<=n;i++)for(j=g[0][x=q[i]];j;j=nxt[0][j])if(f[0][y=v[0][j]]>=f[0][x])f[0][x]=f[0][y]+1;
for(i=n;i;i--)for(j=g[1][x=q[i]];j;j=nxt[1][j])if(f[1][y=v[1][j]]>=f[1][x])f[1][x]=f[1][y]+1;
for(S=n+1,T=S+1,i=1;i<=n;i++)add(S,i),add(i,T);
for(i=1;i<=n;i++)ins(f[0][i],1);
for(fin=i=n;i;i--){
for(j=g[1][x=q[i]];j;j=nxt[1][j])ins(f[1][v[1][j]]+(v[1][j]<=n)+f[0][x],-1);
if((y=ask())<fin)ans=x,fin=y;
for(j=g[0][x];j;j=nxt[0][j])ins(f[0][v[0][j]]+(v[0][j]<=n)+f[1][x],1);
}
return printf("%d %d",ans,fin),0;
}