【codecomb2091】路径数量

2014年10月13日1,2120

题目描述

           给定一张n个点的有向图,求从点1到点n最多有多少条不相交的简单路径。所谓不相交即不经过相同的边的路径。

输入格式

第一行读入一个n,m,表示共n个点,m条边。

接下来m行,每行两个整数x,y,表示从x到y有一条有向边。

输出格式

输出仅包括一行,即最多有多少条不相交的简单路劲。

样例数据 1

输入

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

输出

2

备注

对于20%的数据n<=10,m<=1000;

对于100%的数据n<=1000,m<=100000;

题解

网络流水过