题目描述

小N最近在研究NP完全问题，小O看小N研究得热火朝天，便给他出了一道这样的题目： 有 n 个球，用整数 1 到 n 编号。还有 m 个筐子，用整数1到m编号。 每个球只能放进特定的两个筐子之一，第 i 个球可以放进的筐子记为 Ai 和 Bi 。 每个球都必须放进一个筐子中。 如果一个筐子内有奇数个球，那么我们称这样的筐子为半空的。 求半空的筐子最少有多少个。 小N看到题目后瞬间没了思路，站在旁边看热闹的小I嘿嘿一笑："水题！" 然后三言两语道出了一个多项式算法。 小N瞬间就惊呆了，三秒钟后他回过神来一拍桌子： "不对！这个问题显然是NP完全问题，你算法肯定有错！" 小I浅笑："所以，等我领图灵奖吧!" 小O只会出题不会做题，所以找到了你--请你对这个问题进行探究，并写一个程序解决此题。

输入格式

第一行两个整数 n，m 接下来 n 行，第 i + 1 行有两个整数 Ai ， Bi ，表示第 i 个球可以放的两个筐子。保证 Ai 不等于 Bi 1 <= n，m <= 2 * 10^5，1 <= Ai，Bi <= m

输出格式

第一行一个整数表示半空的筐子的最小值。

4 3
1 2
2 3
1 3
1 2

0
1，3 号球都放在 1 号筐子，2，4 号球都放在 2 号筐子。

提示

各位不妨考虑下，如果要求输出方案应该怎么写.

题目来源

没有写明来源