#10108. 「一本通 3.7 练习 2」Ant Trip

内存限制:32 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 1bentong

题目描述

原题来自:2009 Multi-University Training Contest 12 - Host by FZU

给你无向图的 NN 个点和 MM 条边,保证这 MM 条边都不同且不会存在同一点的自环边,现在问你至少要几笔才能所有边都画一遍。(一笔画的时候笔不离开纸)

输入格式

多组数据,每组数据用空行隔开。
对于每组数据,第一行两个整数 N,MN,M 表示点数和边数。接下去 MM 行每行两个整数 a,ba,b,表示 a,ba,b 之间有一条边。

输出格式

对于每组数据,输出答案。

样例

样例输入

3 3
1 2
2 3
1 3

4 2
1 2
3 4

样例输出

1
2

数据范围与提示

1N105,0M2×105,1a,bN1 \le N \le 10^5,0 \le M \le 2\times 10^5,1 \le a,b \le N