← 返回题目列表

Codeforces · 1037/E

E. 行程

中文机器翻译题面 查看原题

有 $$$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$$$ 当天进行。