提示: 欢迎访问OurACM平台。
Problem 2066 Circuit board layout

Accept: 69    Submit: 225
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

There is a circuit board, the left side and the right side both have N points.

Now we need connect M lines between left point and right. As all we know, the connect line can't intersect, so we need divided the lines into different level, every level the lines are disjoint. Two lines connect one point is not intersect.

Now can you tell kk the minimum level required.

Input

There are multiple tests.

each test first line contain two integer numbers N M(1<=N,M<=100000). next M lines, each line contain two integer x y(1<=x,y<=N), that mean left point x need connect right point y.

Output

Each test output the minimum level required.

Sample Input

3 4 1 2 1 1 2 2 3 1

Sample Output

2

Source

FOJ有奖月赛-2011年12月

Submit  Back  Status  Discuss