#include
using namespace std;
struct edge { int t; edge *next; };
const int maxn = 200009; const int maxe = 300009;
int n, m, vis[maxn], tscc, fs[maxn], cs[maxn], f[2][maxn]; int tpo[maxn], ind[maxn]; edge ebuf_arr[maxe], *ebuf(ebuf_arr), *head[maxn], *hg[maxn];
inline void addEdge(edge** head, int u, int v) { ebuf-> t = v; ebuf-> next = head[u]; head[u] = ebuf ++; }
void tarjanDFS(int po) { static int stc[maxn], stv[maxn], stj[maxn], fr[maxn], d[maxn]; static int dfb[maxn], low[maxn]; int tst(1), dfn(0), tsv(0), tsj(0); vis[stc[tst] = po] = 1; fr[po] = 0; d[po] = 1; while (tst) { int p(stc[tst –]); if (dfb[p]) continue; for (; tsv && d[stv[tsv]] >= d[p]; – tsv) { int q(stv[tsv]); low[fr[q]] = min(low[fr[q]], low[q]); if (dfb[q] == low[q]) { cs[++ tscc] = 0; do { ++ cs[tscc]; fs[stj[tsj]] = tscc; vis[stj[tsj]] = 2; } while (stj[tsj –] != q); } } stv[++ tsv] = stj[++ tsj] = p; low[p] = dfb[p] = ++ dfn; for (edge* e = head[p]; e; e = e-> next) if (!dfb[e-> t]) { d[e-> t] = d[p] + 1; fr[e-> t] = p; vis[e-> t] = 1; stc[++ tst] = e-> t; } else if (vis[e-> t] == 1) low[p] = min(low[p], dfb[e-> t]); } for (; tsv; – tsv) { int q(stv[tsv]); low[fr[q]] = min(low[fr[q]], low[q]); if (dfb[q] == low[q]) { cs[++ tscc] = 0; do { ++ cs[tscc]; fs[stj[tsj]] = tscc; vis[stj[tsj]] = 2; } while (stj[tsj –] != q); } } }
void topSort() { int hd(0), tl(0); memset(ind, 0, sizeof(ind)); for (int i = 1; i <= tscc; ++ i) for (edge* e = hg[i]; e; e = e-> next) ++ ind[e-> t]; for (int i = 1; i <= tscc; ++ i) if (!ind[i]) tpo[tl ++] = i; while (hd < tl) { int p(tpo[hd ++]); for (edge* e = hg[p]; e; e = e-> next) { – ind[e-> t]; if (!ind[e-> t]) tpo[tl ++] = e-> t; } } }
void DP() { int *g; g = f[0]; for (int i = 1; i <= tscc; ++ i) g[i] = -1; g[fs[1]] = 0; for (int i = 0; i < tscc; ++ i) { int p(tpo[i]); if (g[p] > -1) for (edge *e = hg[p]; e; e = e-> next) g[e-> t] = max(g[e-> t], g[p] + cs[e-> t]); } g = f[1]; for (int i = 1; i <= tscc; ++ i) g[i] = -1; g[fs[1]] = 0; for (int i = tscc - 1; i >= 0; – i) { int p(tpo[i]); for (edge *e = hg[p]; e; e = e-> next) if (g[e-> t] > -1) g[p] = max(g[p], g[e-> t] + cs[p]); } }
int main() { #ifndef ONLINE_JUDGE freopen(".in", “r”, stdin); #endif
scanf("%d%d", &n, &m);
memset(head, 0, sizeof(head));
for (int i = 0; i < m; ++ i) {
int u, v;
scanf("%d%d", &u, &v);
addEdge(head, u, v);
}
memset(vis, 0, sizeof(vis));
tscc = 0;
for (int i = 1; i <= n; ++ i)
if (!vis[i])
tarjanDFS(i);
memset(hg, 0, sizeof(hg));
for (int i = 1; i <= n; ++ i)
for (edge* e = head[i]; e; e = e-> next)
if (fs[i] ^ fs[e-> t])
addEdge(hg, fs[i], fs[e-> t]);
topSort();
DP();
int ans(cs[fs[1]]);
for (int i = 1; i <= n; ++ i)
for (edge* e = head[i]; e; e = e-> next)
if (fs[i] != fs[e-> t]) {
int u(fs[i]), v(fs[e-> t]);
if (f[0][v] >= 0 && f[1][u] >= 0)
ans = max(ans, f[1][u] + f[0][v] + cs[fs[1]]);
}
printf("%d\n", ans);
}