You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小Y想要在虚拟世界里造船。最开始 $n$ 个船的完成度全部都为 $0$ 。小Y第 $i$ 时刻可以在 $a_{i}$ 和 $b_{i}$ 两艘船中选择一艘让这艘船的完成度 $+1$ 。

由于国家政府是奇数控，所以所有偶数完成度的船只都将被摧毁，小Y想知道 $m$ 时刻后能剩下来的船只最多有多少艘。

输入格式

第一行两个整数 $n$ 和 $m$

接下来 $m$ 行，每行两个整数 $a_{i}$ , $b_{i}$

样例

input

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

output

6

数据范围与提示

20%的数据，$m≤20,n≤100$

20%的数据，$n≤20,m≤100$

20%的数据，$n≤100,m<=500$

对于100%的数据，$1≤n,m≤200000$