题干：

The bovine population boom down on the farm has caused serious congestion on the cow trails leading to the barn. Farmer John has decided to conduct a study to find the bottlenecks in order to relieve the 'traffic jams' at milking time.

The pasture contains a network of M (1 ≤ M ≤ 50,000) one-way trails, each of which connects exactly two different intersections from the set of N (1 ≤ N ≤ 5,000) intersections conveniently numbered 1..N; the barn is at intersection number N. Each trail connects one intersection point to another intersection point with a higher number. As a result, there are no cycles and, as they say on the farm, all trails lead to the barn. A pair of intersection points might be connected by more than one trail.

During milking time rush hour, the cows start from their respective grazing locations and head to the barn. The grazing locations are exactly those intersection points with no trails connecting into them. Each cow traverses a 'path', which is defined as a sequence of trails from a grazing location to the barn.

Help FJ finding the busiest trail(s) by computing the largest number of possible paths that contain any one trail. The answer is guaranteed to fit in a signed 32-bit integer.

Input

Line 1: Two space-separated integers: N and M. 
Lines 2.. M+1: Two space-separated intersection points.

Output

Line 1: The maximum number of paths passing through any one trail.

Sample Input

7 7
1 3
3 4
3 5
4 6
2 3
5 6
6 7

Sample Output

4

Hint

Here are the four possible paths that lead to the barn: 
1 3 4 6 7 
1 3 5 6 7 
2 3 4 6 7 
2 3 5 6 7

题目大意：

n个点m条有向边，求在入度为零的点到n号点的所有路径中，哪条边被这些路径覆盖的次数最多，求这个次数。题目约定每一条边总是由标号小的连向标号大的。

解题报告：

  本来想dfs，发现不用，，，因为是标号小的连向标号大的，所以直接扫一遍就行了。但是这题不能用vector存边，因为你需要知道这一条边的编号，所以老老实实写结构体。。。正着扫一遍维护经过每一条边的次数和每个顶点的出现次数，同样的倒着扫一遍。最后枚举每一条边，根据乘法原理答案就是两者乘积，维护最大值就行了。这题不能用网络流那种^1的建边方法，因为需要知道反向边的head[u]，所以需要单开数组。

注意可能有重边，比如：

3 3
1 2
1 2
2 3

这组数据就输出2.

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 5000 + 5;
vector<int> vv[MAX],pp[MAX];
int in[MAX],out[MAX],vis[MAX],tot1,tot2,dpV[MAX],dpP[MAX];
int head[MAX],HEAD[MAX];
struct Edge {
	int to,ne,sum;
} e[MAX*10],E[MAX*10];
void add(int u,int v) {
	e[++tot1].to = v;
	e[tot1].ne = head[u];
	head[u] = tot1;
	E[++tot2].to = u;
	E[tot2].ne = HEAD[v];
	HEAD[v] = tot2; 
}
int main()
{
	int n,m;
	cin>>n>>m;
	memset(head,-1,sizeof head);
	memset(HEAD,-1,sizeof HEAD);
	for(int a,b,i = 1; i<=m; i++) {
		scanf("%d%d",&a,&b);
		add(a,b);
		in[b]++;out[a]++;
	}
	for(int i = 1; i<=n; i++) {
		if(in[i] == 0) dpV[i] = 1;
		if(out[i] == 0) dpP[i] = 1;
	}
	for(int cur = 1; cur<=n; cur++) {
		for(int i = head[cur]; ~i; i = e[i].ne) {
			e[i].sum = dpV[cur];
			dpV[e[i].to] += e[i].sum;
		}
	}
	for(int cur = n; cur>=1; cur--) {
		for(int i = HEAD[cur]; ~i; i = E[i].ne) {
			E[i].sum = dpP[cur];
			dpP[E[i].to] += E[i].sum;
		}
	}
	int ans = 0 ;
	for(int i = 1; i<=tot1; i++) {
		ans = max(ans,e[i].sum * E[i].sum);
	}
	printf("%d\n",ans);
	return 0 ;
}