记录编号	416579	评测结果	AAAAAAAAAA
题目名称	165.[USACO Mar07] 奶牛交通	最终得分	100
用户昵称	kZime	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2017-06-22 10:32:55	内存使用	0.82 MiB

# include <bits/stdc++.h>
# define MAXN 5005
using namespace std;

inline char getc() {
    static char buf[1 << 18], *fs, *ft;
    return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}

inline int gn() {
    register int k = 0, f = 1;
    register char c = getc();
    for(; !isdigit(c); c = getc()) if(c == '-') f = -1;
    for(; isdigit(c); c = getc()) k = k * 10 + c - '0';
    return k * f;
}

struct edge { 
    int fr, to;
    edge *ne;
    edge(){;}
    edge(int x, int y, edge *z) { 
        fr = x, to = y, ne = z;
    }
}*head[MAXN * 5], *ahead[MAXN * 5]; 

inline void addedge(int fr, int to, edge **h) { 
    h[fr] = new edge(fr, to, h[fr]);
}

bool hr[MAXN], inq[MAXN];
int f[MAXN], g[MAXN], n, m;
int q[MAXN], l, r;

int dfs(int u, edge **h, int *dp) { 
    if(dp[u]) return dp[u];
    int ans = 0;
    for(edge *e = h[u]; e; e = e->ne) { 
        ans += dfs(e->to, h, dp);
    }
    return dp[u] = ans;
}

int main() { 
# ifndef LOCAL
    freopen("cowtraffic.in", "r", stdin);
    freopen("cowtraffic.out", "w", stdout);
# else 
    freopen("in", "r", stdin);
# endif
    n = gn(), m = gn();
    for(int i = 1; i <= m; i++) { 
        int x = gn(), y = gn();
        addedge(x, y, head);
        addedge(y, x, ahead);
        hr[y] = 1;
    }
    g[n] = 1;
    for(int i = 1; i <= n; i++) { 
        if(!hr[i]) { 
            f[i] = 1;
            dfs(i, head, g);
        }
    }
    dfs(n, ahead, f);
    int ans = 0;
    for(int i = 1; i <= n; i++) { 
        for(edge *e = ahead[i]; e; e = e->ne) { 
            ans = max(ans, f[e->to] * g[e->fr]);
        }
    }
    printf("%d\n", ans);
}