记录编号	464155	评测结果	AAAAAAAAAA
题目名称	[USACO Mar07] 奶牛交通	最终得分	100
用户昵称	Regnig Etalsnart	是否通过	通过
代码语言	C++	运行时间	0.011 s
提交时间	2017-10-25 10:54:58	内存使用	0.50 MiB

#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int maxn=5001;
int n,m,in[maxn],out[maxn],f[maxn],g[maxn],ans=0,i;
vector<int>G[maxn],GG[maxn];
queue<int>Q;
int max(int a,int b){return a>b?a:b;}
void bfs1()
{
	for(i=1;i<=n;i++)if(!in[i])
	{
		f[i]=1;
		Q.push(i);
	}
	while(!Q.empty())
	{
		int now=Q.front();Q.pop();
		for(int j=0;j<G[now].size();j++)
		{
			int to=G[now][j];
			f[to]+=f[now];
			in[to]--;
			if(!in[to])Q.push(to);
		}
	}
	return;
}
void bfs2()
{
	g[n]=1;
	Q.push(n);
	while(!Q.empty())
	{
		int now=Q.front();Q.pop();
		for(int j=0;j<GG[now].size();j++)
		{
			int to=GG[now][j];
			g[to]+=g[now];
			out[to]--;
			if(!out[to])Q.push(to);
		}
	}
	return;
}
int main()
{
	freopen("cowtraffic.in","r",stdin);freopen("cowtraffic.out","w",stdout);
	scanf("%d%d",&n,&m);
	while(m--)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		G[a].push_back(b);
		GG[b].push_back(a);
		in[b]++;
		out[a]++;
	}
	bfs1();
	bfs2();
	for(i=1;i<=n;i++)
	{
		for(int j=0;j<G[i].size();j++)
		{
			int to=G[i][j];
			ans=max(ans,f[i]*g[to]);
		}
	}
	printf("%d\n",ans);
	return 0;
}