← 返回题目列表

Codeforces · 1609/D

D. 社交网络

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

William 参加了一个专门讨论加密货币的会议。社交、结识新朋友以及利用朋友的联系对于了解加密货币世界的最新消息至关重要。

会议有 $$$n$$$ 名参与者,他们最初彼此不熟悉。 William 可以将任何两个之前不熟悉的人 $$$a$$$ 和 $$$b$$$ 互相介绍给对方。

William 有 $$$d$$$ 条件,其中 $$$i$$$ 要求人 $$$x_i$$$ 与人 $$$y_i$$$ 有联系。形式上,如果存在这样一条链 $$$p_1=x, p_2, p_3, \dots, p_k=y$$$,那么两个人 $$$x$$$ 和 $$$y$$$ 就有联系,对于从 $$$1$$$ 到 $$$k - 1$$$ 的所有 $$$i$$$ 来说,确实有两个数字为 $$$p_i$$$ 和 $$$p_{i + 1}$$$互相认识。

对于每 $$$i$$$ ($$$1 \le i \le d$$$),William 希望您计算一个人可以拥有的最大熟人数量,假设 William 满足从 $$$1$$$ 到 $$$i$$$ 的所有条件,并且准确地进行了 $$$i$$$ 介绍。威廉进行了 $$$i$$$ 介绍后,正在检查条件。每个 $$$i$$$ 的答案必须独立计算。这意味着当您计算 $$$i$$$ 的答案时,您应该假设还没有两个人互相介绍。

输入

第一行包含两个整数 $$$n$$$ 和 $$$d$$$ ($$$2 \le n \le 10^3, 1 \le d \le n - 1$$$),分别是人数和条件数。

接下来的 $$$d$$$ 行各包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i \le n, x_i \neq y_i$$$),即根据条件 $$$i$$$ 必须建立连接的人数。

输出

输出 $$$d$$$ 整数。如果威廉进行了 $$$i$$$ 介绍并满足第一个 $$$i$$$ 条件,那么第 $$$i$$$ 个数字必须等于拥有最大可能熟人的人所拥有的熟人数量。

示例

输入 #1

7 6
1 2
3 4
2 4
7 6
6 5
1 7

输出 #1

1
1
3
3
3
6

输入 #2

10 8
1 2
2 3
3 4
1 4
6 7
8 9
8 10
1 4

输出 #2

1
2
3
4
5
5
6
8

注意

第一个测试用例的解释:

在本说明中,圆圈及其中的数字表示具有相应数字的人。该线表示威廉介绍了两个有联系的人。红色标记的人是最熟人。这些并不是唯一正确的介绍人的方式。