2498: LQ1177 收集宝石

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

要收集最多宝石,但是几乎每一颗魔法宝石都会和另外一颗宝石相冲。相冲表示这两颗宝石不能同时拥有。例如,宝石A和宝石B相冲,那么,你可以选择两宝石都不收集,也可以只收集宝石A或者只收集宝石B,但不能同时拥有宝石A和宝石B。现在给定了游戏里宝石的数量N ( 2<N<100 ),宝石从1N依次编号并给出M(2<M<2000 ) 相冲的宝石编号,请帮聪聪计算出最多能够收集到多少颗宝石。

Input

第一行输入两个正整数NM,分别表示游戏里的宝石数量和M对相冲的宝石,两个正整数之间用一个空格隔开接下来输入M行,每行两个正整数,分别表示相冲的两颗宝石的编号,两个正整数之间用一个空格隔开。

Output

输出一个整数,表示最多宝石数。

Sample Input Copy

6 8
1 2
2 3
2 4
2 5
2 6
3 4
4 5
5 6

Sample Output Copy

3