CF1609D.Social Network

William arrived at a conference dedicated to cryptocurrencies. Networking, meeting new people, and using friends' connections are essential to stay up to date with the latest news from the world of cryptocurrencies.

The conference has $n$ participants, who are initially unfamiliar with each other. William can introduce any two people, $a$ and $b$, who were not familiar before, to each other.

William has $d$ conditions, $i$'th of which requires person $x_i$ to have a connection to person $y_i$. Formally, two people $x$ and $y$ have a connection if there is such a chain $p_1=x, p_2, p_3, \dots, p_k=y$ for which for all $i$ from $1$ to $k - 1$ it's true that two people with numbers $p_i$ and $p_{i + 1}$ know each other.

For every $i$ ($1 \le i \le d$) William wants you to calculate the maximal number of acquaintances one person can have, assuming that William satisfied all conditions from $1$ and up to and including $i$ and performed exactly $i$ introductions. The conditions are being checked after William performed $i$ introductions. The answer for each $i$ must be calculated independently. It means that when you compute an answer for $i$, you should assume that no two people have been introduced to each other yet.

威廉参加了一场专注于加密货币的会议。拓展人脉、结识新朋友以及借助朋友的关系网，对于及时掌握加密货币领域的最新动态至关重要。

本次会议共有 $n$ 名参与者，他们最初彼此互不相识。威廉可以将任意两个此前互不相识的人 $a$ 和 $b$ 相互介绍认识。

威廉有 $d$ 个条件，其中第 $i$ 个条件要求人员 $x_i$ 与人员 $y_i$ 之间存在“连接”。形式化地，两个人 $x$ 和 $y$ 存在连接，当且仅当存在一条链 $p_1=x, p_2, p_3, \dots, p_k=y$，使得对所有 $i$（$1 \le i \le k - 1$），编号为 $p_i$ 和 $p_{i + 1}$ 的两人彼此相识。

对每个 $i$（$1 \le i \le d$），你需要计算：在威廉恰好执行了 $i$ 次介绍、且满足前 $i$ 个条件（即第 $1$ 至第 $i$ 个条件）的前提下，单个人最多能拥有的熟人数量。注意：这些条件是在威廉完成第 $i$ 次介绍后被检验的。对每个 $i$ 的答案必须独立计算。这意味着，在计算第 $i$ 个答案时，应假设此时尚无任何两人被相互介绍过。

The first line contains two integers $n$ and $d$ ($2 \le n \le 10^3, 1 \le d \le n - 1$), the number of people, and number of conditions, respectively.

Each of the next $d$ lines each contain two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n, x_i \neq y_i$), the numbers of people which must have a connection according to condition $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$ 个条件所要求必须建立连接的两个人的编号。

Output $d$ integers. $i$th number must equal the number of acquaintances the person with the maximal possible acquaintances will have, if William performed $i$ introductions and satisfied the first $i$ conditions.

输出 $d$ 个整数。其中第 $i$ 个数必须等于：若 William 进行了 $i$ 次介绍并满足前 $i$ 个条件，则拥有最多熟人的那个人所拥有的熟人数量。

The explanation for the first test case:

In this explanation, the circles and the numbers in them denote a person with the corresponding number. The line denotes that William introduced two connected people. The person marked with red has the most acquaintances. These are not the only correct ways to introduce people.

第一个测试用例的解释：

在本解释中，圆圈及其内部的数字表示对应编号的人；连线表示威廉将两个相连的人相互介绍。标为红色的人拥有最多熟人。这些并非唯一正确的介绍方式。