CF1609D Social Network

William 来到了一场关于加密货币的会议。社交、结识新朋友以及利用朋友的关系网对于及时了解加密货币世界的最新消息至关重要。 会议共有 $n$ 名参与者，起初他们彼此都不认识。William 可以介绍任意两位之前互不相识的人 $a$ 和 $b$ 认识。 William 有 $d$ 个条件，第 $i$ 个条件要求编号为 $x_i$ 的人与编号为 $y_i$ 的人之间必须有一条关系链。具体来说，如果存在一条链 $p_1=x, p_2, p_3, \dots, p_k=y$，使得对于所有 $1 \le i \le k-1$，编号为 $p_i$ 和 $p_{i+1}$ 的两个人彼此认识，则称 $x$ 和 $y$ 之间有关系。 对于每个 $i$（$1 \le i \le d$），William 希望你计算在满足前 $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$ 个条件要求编号为 $x_i$ 和 $y_i$ 的人之间必须有关系。

输出 $d$ 个整数。第 $i$ 个数表示在进行了 $i$ 次介绍并满足前 $i$ 个条件后，某个人可能拥有的最大熟人数量。

第一个测试用例的解释： 在下图中，圆圈及其中的数字表示对应编号的人。连线表示 William 介绍了两位相连的人。用红色标记的人拥有最多的熟人。这些并不是唯一正确的介绍方式。  由 ChatGPT 4.1 翻译