Background

Description

母舰的高能瓦斯不足，因此指挥官想要传送一些探测机器去收集这些资源。目前已经探测到N处高能瓦斯资源，部分资源间有单向道路连结，一共有M条单向道路。为了提高效率，指挥官决定一次传送多个探测机器，同时对资源进行收集。但是考虑到探测机器还有其他工作任务，因此指挥官希望你能制定一个传送方案，使得使用的探测机器数量尽可能少。
探测机器会被传送到某一个资源处，根据预定的路线行进并收集资源，然后再被传送回母舰。值得注意的是，即使某地的资源已经被收集完毕，探测机器仍然可以进入该区域，并通过从该区域出发的单向道路进入其他资源区域。探测机器可以经过某处高能瓦斯资源但不收集。探测机器能够收集的容量足够大，因此不会出现无法携带更多资源的情况。

Format

Input

输入包含多组数据，每组数据第一行包含两个整数N,M,1≤N≤500,0≤M≤5000。接下来的M行包含两个整数A,B,1≤A,B≤N，代表存在A到B的单向道路。输入以两个0结束。
保证输入没有重边，也不存在环。
输入保证sum N<=500

Output

对于每一个输入样例，需要输出所需的最少的探测机器的数量。

Sample 1

Input

1 0
2 1
1 2
2 0
0 0

Output

1
1
2

Limitation

2s, 65536KiB for each test case.