传奇农夫约翰正在举办一场盛大的派对,来自世界各地的动物都在他的家里闲逛。他的客人饿了,所以他指示他的牛贝西把零食拿出来!哞!
有 $$$n$$$ 种零食口味,用整数 $$$1、2、\ldots、n$$$ 编号。贝西有 $$$n$$$ 零食,每种口味一份零食。每个客人都有两种最喜欢的口味。吃零食的程序如下:
- 首先,Bessie 会以某种方式让客人排队。
- 然后按照这个顺序,客人将一件一件地接近零食。
- 每个客人都会轮流吃掉所有剩余的他们最喜欢的口味的零食。如果客人上去时没有喜欢的口味,他们就会很伤心。
以最佳方式排列客人,帮助贝西最大限度地减少悲伤客人的数量。
输入
第一行包含整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le k \le 10^5$$$)、零食数量和客人数量。
以下 $$$k$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$, $$$x_i \ne y_i$$$),即第 $$$i$$$ 位客人最喜欢的零食口味。
输出
输出一个整数,悲伤客人的最小数量。
示例
输入 #1
5 4 1 2 4 3 1 4 3 4
输出 #1
1
输入 #2
6 5 2 3 2 1 3 4 6 5 4 5
输出 #2
0
注意
在第一个示例中,Bessie 可以这样对客人进行排序:$$$3, 1, 2, 4$$$。客人 $$$3$$$ 首先吃零食 $$$1$$$ 和 $$$4$$$。然后客人$$$1$$$去只吃零食$$$2$$$,因为零食$$$1$$$已经被吃掉了。同样,客人$$$2$$$ 上去只吃了零食$$$3$$$。所有的零食都没有了,所以客人$$$4$$$会很难过。
在第二个示例中,一个最佳排序是 $$$2, 1, 3, 5, 4$$$。所有的客人都会感到满意。