Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 2066
Selective Course

Time Limit: 2 Seconds      Memory Limit: 65536 KB

On the 18th week of each semester, teacher should schedule their exames. There are at most 200 elective courses. And each student could select at most 2 courses one semester. School always schedule 2 exam times a day, 8:30 - 10:30 in the morning and 3:00-5:00 in the afternoon.

Your task is to calculate the mininum exam times.


Input

The input consists of several testcases.

In each test case, the first line contains n and m, n for the number of elective course , m ( 0 < m <= 2000) for the number of student. Followed m line, each line gives two integer coursei and coursej (coursei != coursej) which indicate the courses selected by mth student.

Process to the end of file.


Output

For each testcase, exactly one line of output containing a single integer value is to be produced.


Sample Input

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


Sample Output

3



Author: CHEN, Hong
Source: ZOJ Monthly, January 2004
Submit    Status