There is certain amount of night guards that are available to protect the local junkyard from possible junk robberies. These guards need to scheduled in pairs, so that each pair guards at different night. The junkyard CEO ordered you to write a program which given the guards characteristics determines the maximum amount of scheduled guards (the rest will be fired). Please note that each guard can be scheduled with only one of his colleagues and no guard can work alone.
There will be a number of test cases in the input.
The first line of each testcase contains two numbers N ≤ 222, and M ≤ 1000, which is the amount of night guards. Next M lines consisting of unordered pairs (i, j) follow, each such pair means that guard #i and guard #j can work together, because it is possible to find uniforms that suit both of them (The junkyard uses different parts of uniforms for different guards i.e. helmets, pants, jackets. It is impossible to put small helmet on a guard with a big head or big shoes on guard with small feet). The input ends with Eof. The input may contain duplicated pairs, but all pairs are promised to have different i and j.
For each test case output the even number C, the amount of scheduled guards.
3 3 1 2 2 3 1 3 1 0
2 0
Migrated from old NTUJ.
Ural 1099
| No. | Testdata Range | Score |
|---|