有 $$$n$$$ 个人最初互相不认识。每天早上,他们两个原本不是朋友的人就成为了朋友。
我们想为 $$$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$$$ ($$$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$$$ 可以参加行程的最大人数。
示例
输入 #1
4 4 2 2 3 1 2 1 3 1 4
输出 #1
0 0 3 3
输入 #2
5 8 2 2 1 4 2 5 4 5 2 4 3 5 1 4 1 3 2
输出 #2
0 0 0 3 3 4 4 5
输入 #3
5 7 2 1 5 3 2 2 5 3 4 1 2 5 3 1 3
输出 #3
0 0 0 0 3 4 4
注意
在第一个示例中,
- $$$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$$$ 当天进行。