签到题

Time Limit: 1000ms

Memory Limit: 65535kb

Description

给一个有向无环图,求从1号点走到N号点有多少种不同的路径。

Input

多组数据,每组第一行是N(2<=N<=100)和M(N-1<=M<=10000),表示顶点数和边数,顶点的编号从1到N。之后M行每行有两个数字a和b,表示从顶点a到顶点b有一条边。以EOF结尾。

Output

对于每组输入数据,输出一行,包含一个整数,表示从1号点到N号点有多少条不同的路径。

Sample Input

2 1
1 2
4 4
1 2
2 4
1 3
3 4

Sample Output

1
2

Hint


Source

tsfn

提交代码