CF1037E.Trips

There are $n$ persons who initially don't know each other. On each morning, two of them, who were not friends before, become friends.

We want to plan a trip for every evening of $m$ days. On each trip, you have to select a group of people that will go on the trip. For every person, one of the following should hold:

• Either this person does not go on the trip,
• Or at least $k$ of his friends also go on the trip.

Note that the friendship is not transitive. That is, if $a$ and $b$ are friends and $b$ and $c$ are friends, it does not necessarily imply that $a$ and $c$ are friends.

For each day, find the maximum number of people that can go on the trip on that day.

有 $n$ 个人，最初彼此互不相识。每天早晨，其中两人（此前不是朋友）成为朋友。

我们需要为连续 $m$ 天的每个傍晚安排一次旅行。每次旅行中，你需要选出一组人参加旅行。对每个人而言，以下条件之一必须成立：

• 该人不参加此次旅行；
• 或者该人的至少 $k$ 位朋友也参加了此次旅行。

注意：朋友关系不具备传递性。即，若 $a$ 与 $b$ 是朋友、$b$ 与 $c$ 是朋友，并不能推出 $a$ 与 $c$ 是朋友。

对每一天，请计算当天旅行中最多能有多少人参加。

The first line contains three integers $n$, $m$, and $k$ ($2 \leq n \leq 2 \cdot 10^5, 1 \leq m \leq 2 \cdot 10^5$, $1 \le k \lt n$) — the number of people, the number of days and the number of friends each person on the trip should have in the group.

The $i$-th ($1 \leq i \leq m$) of the next $m$ lines contains two integers $x$ and $y$ ($1\leq x, y\leq n$, $x\ne y$), meaning that persons $x$ and $y$ become friends on the morning of day $i$. It is guaranteed that $x$ and $y$ were not friends before.

第一行包含三个整数 $n$、$m$ 和 $k$（$2 \leq n \leq 2 \cdot 10^5$，$1 \leq m \leq 2 \cdot 10^5$，$1 \le k \lt n$），分别表示人数、天数以及旅行团中每个人应拥有的朋友数量。

接下来的 $m$ 行中，第 $i$ 行（$1 \leq i \leq m$）包含两个整数 $x$ 和 $y$（$1\leq x, y\leq n$，$x\ne y$），表示在第 $i$ 天早晨，人员 $x$ 与 $y$ 成为朋友。保证 $x$ 与 $y$ 在此之前并非朋友。

Print exactly $m$ lines, where the $i$-th of them ($1\leq i\leq m$) contains the maximum number of people that can go on the trip on the evening of the day $i$.

恰好输出 $m$ 行，其中第 $i$ 行（$1\leq i\leq m$）包含第 $i$ 天晚上能够参加旅行的最大人数。

In the first example,

• $1,2,3$ can go on day $3$ and $4$.

In the second example,

• $2,4,5$ can go on day $4$ and $5$.
• $1,2,4,5$ can go on day $6$ and $7$.
• $1,2,3,4,5$ can go on day $8$.

In the third example,

• $1,2,5$ can go on day $5$.
• $1,2,3,5$ can go on day $6$ and $7$.

在第一个例子中，

• $1,2,3$ 可以在第 $3$ 天和第 $4$ 天参加。

在第二个例子中，

• $2,4,5$ 可以在第 $4$ 天和第 $5$ 天参加。
• $1,2,4,5$ 可以在第 $6$ 天和第 $7$ 天参加。
• $1,2,3,4,5$ 可以在第 $8$ 天参加。

在第三个例子中，

• $1,2,5$ 可以在第 $5$ 天参加。
• $1,2,3,5$ 可以在第 $6$ 天和第 $7$ 天参加。