Problem: King Arthur II

Want to try solving this problem? You can submit your code online if you log in or register.

King Arthur II

Input File: arthin.txt
Output File: arthout.txt
Time Limit: 3 seconds

It has been many years since King Arthur has held a meeting for the Knights of the Round Table. Despite his best efforts to arrange seating in order to minimise conflict between knights, the last meeting deteriorated into a chaos of insulting and duelling unfit for the honourable dining room of Camelot.

Arthur must bring his knights together again, for rumour has spread throughout the kingdom that the dragons are becoming restless. In order to avoid the disasters of the last meeting, Arthur has decided to hold two meetings instead of one, and ensure that no two knights who would likely duel each other are invited to the same meeting. Furthermore, since immediate anti-dragon action is required, Arthur would like to have as many knights as possible at the first meeting.

After making a long list of all the knights and all the pairs of knights who may duel if invited to the same meeting, Arthur has requested you as the Court Informatician to write a program determining the largest number of knights that can be invited to the first meeting such that no pair of knights likely to duel each other are invited to the same meeting. Merlin, in his infinite wisdom, has assured you that there is at least one way of dividing all the knights into two meetings without any chance of duelling at either meeting.

Input

Your program should read from the file arthin.txt.

The first line of input will contain N, the number of knights.
The second line of input will contain P, the number of pairs of duel-prone knights.
Each of the following P lines will contain two space-separated integers a and b, representing two knights who cannot be invited to the same meeting. It is guaranteed that a b and that the same pair will not appear twice in the input. Knights are labelled from 1 to N.

Output

Your program should write to the file arthout.txt. It should output a single integer: the maximum number of knights that can be invited to the first meeting without any chance of a duel occurring at either the first or second meeting.

Sample Input

Sample Output

Explanation

In this example, Arthur can invite knights 2, 4, 5, 7 and 8 to the first meeting and knights 1, 3 and 6 to the second meeting. There is no way for Arthur to invite more than 5 knights to the first meeting without risking the chance of a duel between knights, so 5 is the correct answer.

Constraints

To evaluate your solution, the judges will run your program against several different input files. All of these files will adhere to the following bounds:

1 ≤ N ≤ 100,000
0 ≤ P ≤ 1,000,000

As some of the test cases will be quite large, you may need to think about how well your solution scales for larger input values. However, not all the cases will be large. In particular:

For 20% of cases, N ≤ 20.

Scoring

The score for each input scenario will be 100% if the correct answer is written to the output file, and 0% otherwise.