题目描述

在某高校的ACM实验室中，有 $n$ 名队员。起初，他们彼此之间并不认识。由于XCPC的比赛都是三人团队赛，教练决定在接下来的 $m$ 天内，每天早上安排两位之前互不认识的队员建立协作关系。

每个晚上，实验室需要组织一次协作训练。参与该训练的队员应尽可能多，但这时实验室的所有人必须满足以下规则：

• 要么这位队员不参加协作训练。

• 要么他参加协作训练，并且至少有 $k$ 位他已经建立协作关系的队员也参与了该日的训练。

注意：协作关系不是传递的。如果队员 $a$ 与 $b$ 建立了协作关系，$b$ 与 $c$ 建立了协作关系，并不意味着 $a$ 与 $c$ 之间也有协作关系。

教练想知道：对于每一天，有多少人可以参加协作训练？

输入格式

第一行包含三个整数 $n$ 、 $m$ 和 $k$ （ $2 \leq n \leq 2 \cdot 10^5, 1 \leq m \leq 2 \cdot 10^5$，$1 \le k < n$）--人数、天数和每个人在协作训练中应该有协作关系的人数。

接下来 $m$ 行的 $i$ /-th ( $1 \leq i \leq m$ )包含两个整数 $x$ 和 $y$ （ $1\leq x, y\leq n$ , $x\ne y$ ），这意味着 $x$ 和 $y$ 在第 $i$ 天早上建立了协作关系。可以肯定， $x$ 和 $y$ 之前不是协作的关系。

输出格式

输出 $m$ 行，其中的 $i$ 行（ $1\leq i\leq m$ ）表示第 $i$ 天晚上可以参加协作训练的最大人数。

样例

4 4 2
2 3
1 2
1 3
1 4

0
0
3
3

5 8 2
2 1
4 2
5 4
5 2
4 3
5 1
4 1
3 2

0
0
0
3
3
4
4
5

提示

对于第一组样例，第1、2天没人满足条件，第3、4天，队员1、2、3都满足条件。