考试的时候忘了缩点，人为dfs模拟缩点，没想到竟然跑了30分，RB爆发。。。
边是可以重复走的，所以在同一个强连通分量里，无论从那个点进入从哪个点出，所有的点一定能被一条路走到。 要使用缩点。
然后我们枚举每一条边，考虑如果将这条边反置的话，就是这条边的终点到1的点的权值（正向的）加上起点到1的点的权值（反向的）；例：→→←→→
每个点到1的正向反向距离可以用两遍SPFA解决出来。
先使用tarjan缩点，记录每个点的权值，缩点后权值变为强连通分量中点的个数。缩完点之后重新建图，正向边存1，反向边存-1；
注意：在枚举每一条边求MAX时一定要判断它的起点和终点能否到达1。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
#define pos(i,a,b) for(int i=(a);i<=(b);i++)
#define pos2(i,a,b) for(int i=(a);i>=(b);i--)
#define N 501000
int n,m;
struct haha
{
int next,to,w;
};
haha edgechu[N],edge[N];
int head[N],headchu[N],cnt=1,cntchu=1,cntt,hea;
int belong[N],low[N],dfn[N],ji=1,stack[N],instack[N];
int point[N];
void add(int u,int v,int w)
{
edge[cnt].to=v;
edge[cnt].next=head[u];
edge[cnt].w=w;
head[u]=cnt++;
}
void addchu(int u,int v,int w)
{
edgechu[cntchu].to=v;
edgechu[cntchu].next=headchu[u];
edgechu[cntchu].w=w;
headchu[u]=cntchu++;
}
void tarjan(int now)
{
low[now]=dfn[now]=ji;
ji++;
stack[++hea]=now;
instack[now]=1;
for(int v=headchu[now];v;v=edgechu[v].next)
{
int i=edgechu[v].to;
if(dfn[i]==-1)
{
tarjan(i);
low[now]=min(low[now],low[i]);
}
else
if(instack[i])
low[now]=min(low[now],dfn[i]);
}
if(low[now]==dfn[now])
{
cntt++;
int temp;
while(1)
{
temp=stack[hea--];
belong[temp]=cntt;
point[cntt]++;
instack[temp]=0;
//cout<<"temp="<<temp<<" cntt="<<cntt<<endl;
if(temp==now)
break;
}
}
}
int diszheng[N],disfan[N];
int flag[N];
void spfazheng(int x)
{
queue<int> q;
pos(i,1,n)
diszheng[i]=0;
memset(flag,0,sizeof(flag));
diszheng[x]=point[x];
q.push(x);
flag[x]=1;
int k;
while(!q.empty())
{
k=q.front();
for(int v=head[k];v;v=edge[v].next)
{
int i=edge[v].to;
if(edge[v].w>0&&diszheng[i]<diszheng[k]+point[i])
{
diszheng[i]=diszheng[k]+point[i];
if(!flag[i])
{
q.push(i);
flag[i]=1;
}
}
}
flag[q.front()]=0;
q.pop();
}
}
void spfafan(int x)
{
queue<int> q;
pos(i,1,n)
disfan[i]=0;
memset(flag,0,sizeof(flag));
disfan[x]=point[x];
q.push(x);
flag[x]=1;
int k;
while(!q.empty())
{
k=q.front();
for(int v=head[k];v;v=edge[v].next)
{
int i=edge[v].to;
if(edge[v].w<0&&disfan[i]<disfan[k]+point[i])
{
disfan[i]=disfan[k]+point[i];
if(!flag[i])
{
q.push(i);
flag[i]=1;
}
}
}
flag[q.front()]=0;
q.pop();
}
}
struct qian
{
int from,to;
}cun[N];
int road;
int ans;
int main()
{
//freopen("cown.in","r",stdin);
//freopen("cown.out","w",stdout);
scanf("%d%d",&n,&m);
memset(dfn,-1,sizeof(dfn));
pos(i,1,m)
{
int x,y;
scanf("%d%d",&x,&y);
addchu(x,y,1);
}
pos(i,1,n)
if(dfn[i]==-1)
tarjan(i);
pos(i,1,n)
for(int v=headchu[i];v;v=edgechu[v].next)
{
int j=edgechu[v].to;
if(belong[i]!=belong[j])
{
add(belong[i],belong[j],1);
add(belong[j],belong[i],-1);
cun[++road].from=belong[i];
cun[road].to=belong[j];
}
}
spfafan(belong[1]);spfazheng(belong[1]);
/*pos(i,1,cntt)
cout<<"diszheng[i]="<<diszheng[i]<<" disfan[i]="<<disfan[i]<<endl;*/
pos(i,1,road)
{
if(diszheng[cun[i].to]>0&&disfan[cun[i].from]>0)
ans=max(ans,diszheng[cun[i].to]+disfan[cun[i].from]-point[belong[1]]);
//cout<<"ans="<<ans<<endl;
}
printf("%d",ans);
//while(1);
return 0;
}