← 返回题目列表

Codeforces · 1209/D

D. 牛和零食

中文机器翻译题面 查看原题

传奇农夫约翰正在举办一场盛大的派对,来自世界各地的动物都在他的家里闲逛。他的客人饿了,所以他指示他的牛贝西把零食拿出来!哞!

有 $$$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$$$。所有的客人都会感到满意。