题目描述：
“最短的捷径就是绕远路，绕远路就是我最短的捷径”
转眼就Stage X 了，Stage X 的比赛路线可以看做一个n 个点m 条边的有向无环图，
每条边长度都是1。杰洛·齐贝林会选择走最长的那一条路径。
迪亚哥·布兰度决定摧毁一个城市以及所有关于该城市的边，由于变成恐龙后脑子有
点问题，他想要让摧毁后的Stage 最长路径最短，他想知道要摧毁哪个城市，及摧毁后
最长路径的长度，如果有多个城市答案相同，则输出编号最小的那一个。
输入：
本题包含多组数据，输入第一行一个整数T 代表数据组数
每组数据第一行两个整数n,m 表示点数，边数。
每组数据第2~m+1 行每行两个整数xi,yi 表示有一条连接xi,yi 的边。
输出：
对于每组数据，输出一行两个整数，表示删除的城市编号及删除该城市后最长
路径的长度。
数据范围：
对于所有数据，满足T≤10，1≤n≤100000，0≤m≤500000。
算法标签：拓扑+线段树（stl优先队列维护会被卡成80）
思路：
经过每一个点的最长路径可以表示成我的入度经过的走到我的最远距离，走出我的最远距离，于是根据拓扑序，每次把点模拟成一堆在s集合按拓扑序移动到t集合，维护其中的最长线段，用线段树维护。
以下代码：
#include<bits/stdc++.h> #define il inline #define _(d) while(d(isdigit(ch=getchar()))) using namespace std; const int N=1e5+5,M=5e5+5; int ans,m,n,head[2][N],ne[M<<1],to[M<<1],cnt,out[N],q[N],r,l,in[N]; int f[N],g[N],id,maxn[N<<2],c[N];char ch; int read(){int x;_(!);x=ch^48;_()x=(x<<1)+(x<<3)+(ch^48);return x;} il void insert(int op,int x,int y){ne[++cnt]=head[op][x];head[op][x]=cnt;to[cnt]=y;} il void ins(int x,int l,int r,int pos,int v){if(l==r){c[l]+=v;if(c[l]>0)maxn[x]=l;else c[l]=0,maxn[x]=-1;return;}int mid=(l+r)>>1;if(pos<=mid)ins(x<<1,l,mid,pos,v);else ins(x<<1|1,mid+1,r,pos,v);maxn[x]=max(maxn[x<<1],maxn[x<<1|1]); } int main() {int T=read();while(T--){n=read();m=read();ans=n;l=0;r=0;id=1;for(int i=1;i<=n;i++)head[0][i]=head[1][i]=0,out[i]=f[i]=g[i]=c[i]=in[i]=0;cnt=0;for(int i=1;i<=(n<<2);i++)maxn[i]=0;while(m--){int x,y;x=read();y=read();insert(0,x,y);insert(1,y,x);in[y]++;out[x]++;}for(int i=1;i<=n;i++)if(!out[i])q[++r]=i;while(l<r){int x=q[++l];for(int i=head[1][x];i;i=ne[i]){if(g[to[i]]<g[x]+1)g[to[i]]=g[x]+1;if(--out[to[i]]==0)q[++r]=to[i];}}l=0;r=0;for(int i=1;i<=n;i++)if(!in[i])q[++r]=i;while(l<r){int x=q[++l];for(int i=head[0][x];i;i=ne[i]){if(f[to[i]]<f[x]+1)f[to[i]]=f[x]+1;if(--in[to[i]]==0)q[++r]=to[i];}}for(int i=1;i<=n;i++)ins(1,0,n,g[i],1);for(int i=1;i<=n;i++){int x=q[i];for(int j=head[1][x];j;j=ne[j])ins(1,0,n,f[to[j]]+1+g[x],-1);ins(1,0,n,g[x],-1);if(maxn[1]<ans||(ans==maxn[1]&&q[i]<id))ans=maxn[1],id=q[i];for(int j=head[0][x];j;j=ne[j])ins(1,0,n,f[x]+1+g[to[j]],1);ins(1,0,n,f[x],1);}printf("%d %d\n",id,ans);} return 0; }
