#include<iostream> #include<vector> #include <cstring> #include <set> #include<cstdio> using namespace std; const int MAX=100011; int Stop;//栈中的元素个数 int cnt;//记录连通分量的个数 int visitNum;//记录遍历的步数 int DFN[MAX]; //记录节点u第一次被访问时的步数 int LOW[MAX]; //记录与节点u和u的子树节点中最早的步数 bool instack[MAX];//记录节点u是否在栈中 int Stap[MAX];//栈 int Belong[MAX];//记录每个节点属于的强连通分量编号 int N;//节点个数 vector<int> tree[MAX],scc[MAX]; void tarjan(int i) { int j; DFN[i]=LOW[i]=++visitNum; instack[i]=true; Stap[++Stop]=i;//将当前节点压入栈中 for (unsigned k=0;k<tree[i].size();k++) { j=tree[i][k]; if (!DFN[j]) { tarjan(j); if (LOW[j]<LOW[i]) LOW[i]=LOW[j]; } else if (instack[j] && DFN[j]<LOW[i]) LOW[i]=DFN[j]; } if (DFN[i]==LOW[i]) { cnt++; // cout<<"连通分量"<<cnt<<": "; scc[cnt].clear(); do { j=Stap[Stop--]; instack[j]=false; // cout<<j<<" "; scc[cnt].push_back(j); Belong[j]=cnt; } while (j!=i); // cout<<endl; } } int deg[MAX]; vector<int> son[MAX]; set<int> VIS; void solve() { Stop=cnt=visitNum=0; memset(DFN,0,sizeof(DFN)); for (int i=1;i<=N;i++) if (!DFN[i])//有可能图不是连通图 tarjan(i); for(int i=1;i<=cnt;i++){ son[i].clear(); VIS.clear(); deg[i] = scc[i].size(); // cout<<i<<" "<<deg[i]<<": "; for(int j=0;j<scc[i].size();j++){ int u = scc[i][j]; for(int k=0;k<tree[u].size();k++){ if(Belong[tree[u][k]]!=i && !VIS.count(Belong[tree[u][k]])){ VIS.insert(Belong[tree[u][k]]); son[i].push_back(Belong[tree[u][k]]); // cout<<Belong[tree[u][k]]<<" "; } } } // cout<<endl; } } int c[MAX],t,topo[MAX]; bool Dfs(int u){ c[u] = -1; for(int i=0;i<son[u].size();i++){ int v = son[u][i]; if(c[v] < 0) return false; else if(!c[v] && !Dfs(v)) return false; } c[u] = 1; topo[--t]=u; return true; } bool toposort(){ t = cnt; memset(c,0,sizeof(c)); for(int u = 1;u<=cnt;u++) if(!c[u]){ if(!Dfs(u)) return false; } return true; } int d[MAX],vv[MAX]; int dp(int u,int fa){ if(vv[u]) return d[u]; vv[u]=1; int res = deg[u]; for(int i=0;i<son[u].size();i++)if(son[u][i]!=fa){ res = max(res,dp(son[u][i],u)+deg[u]); } return d[u] = res; } int main() { int m; while(scanf("%d %d",&N,&m)==2){ for(int i=1;i<=N;i++) tree[i].clear(); for(int i=1;i<=m;i++){ int x,y; scanf("%d %d",&x,&y); tree[x].push_back(y); } solve(); toposort(); int res = 0; memset(vv,0,sizeof(vv)); for(int i=0;i<cnt;i++){ int u = topo[i]; if(!vv[u]){ res = max(res,dp(u,-1)); //if(res == 7) cout<<u<<"**\n"; } } printf("%d\n",res); } return 0; } /* 6 8 1 2 1 3 3 4 4 1 2 4 4 6 3 5 5 6 6 */