UOJ Logo

NOI.AC

1S 512MB

#712. 练级

统计

B. 练级

题目描述

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

由于某些奇怪的原因,你希望最终等级为奇数的船只数量最大,请问能达到多少?

输入格式

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

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

输出格式

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

样例输入

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

样例输出

6

数据限制

对于20%的数据,$m \leq 20,n \leq 100$

对于另外20%的数据,$n \leq 20,m \leq 100$

对于100%的数据,$1 \leq n,m \leq 200000,1 \leq u_i,v_i \leq n$