P2096 [第三章习题7.2]Ant Trip
描述
蚂蚁国家由N个城镇组成。有M条公路连接城镇。
蚂蚁托尼和他的朋友们想要经历这个国家的每一个角落。
他们打算访问每一条道路，每条道路必须准确地访问一次。但是，对于一群人来说，这可能是不可能完成的任务。所以他们试图将所有人分成几个小组，每个人都可以开始在不同的城镇。现在，托尼想要知道为实现目标需要形成的最少的蚂蚁群体。
蚂蚁托尼和他的朋友们想要经历这个国家的每一个角落。
他们打算访问每一条道路，每条道路必须准确地访问一次。但是，对于一群人来说，这可能是不可能完成的任务。所以他们试图将所有人分成几个小组，每个人都可以开始在不同的城镇。现在，托尼想要知道为实现目标需要形成的最少的蚂蚁群体。
输入
包含多个数据，由几个空行分隔。每个测试用例以两个整数N（1 <= N <= 100000），M（0 <= M <= 200000）开始，表示有N个城镇和M个道路。
接下来的M行，每行包含两个整数a，b，（1 <= a，b <= N）表示有连接城镇a和城镇b的道路。
接下来的M行，每行包含两个整数a，b，（1 <= a，b <= N）表示有连接城镇a和城镇b的道路。
输出
每个测试用例，输出需要形成的最少的组来实现他们的目标。
样例输入
3 3
1 2
2 3
1 3
4 2
1 2
3 4
样例输出
1 2
