Home => ProblemSet => 100.101-02:练级
Problem1302--100.101-02:练级

1302: 100.101-02:练级

Time Limit: 1 Sec  Memory Limit: 512 MB  Submit: 2  Solved: 2
[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]

Description

有n张卡片,编号为1到n,初始等级均为0。有m次练级机会,第i次必须从u_i,v_i两个编号的卡片中选择一个(u_i可能与v_i相等),使其等级增加1。

你希望最终等级为奇数的卡片数量最大,请问最多能有多少张?

Input

第一行两个用空格隔开的整数n,m

之后m行每行包含两个用空格隔开的整数,为u_i,v_i

Output

一个整数,表示奇数等级船只的最大数量

Sample Input Copy

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

Sample Output Copy

6

HINT

对于20%的数据,m <= 20,n <= 100

对于另外20%的数据,n <= 20,m <= 100

对于100%的数据,1 <= n,m <= 200000,1 <= u_i,v_i <= n

Source/Category