← 返回题目列表

Codeforces · 1488/I

I. 恶魔入侵

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

达拉然是一座飞行的魔法之城。它由 $$$n$$$ 浮岛组成,由 $$$m$$$ 桥梁连接(每座桥梁都可以双向穿过)。沿着这些桥梁可以到达每个岛屿。如果某个魔法实验出了严重的错误,这座宏伟的城市被毁掉了,那就太可惜了,对吧?

好吧,猜猜发生了什么。通往恶魔领域的传送门在 $$$1$$$ 岛上打开。这是灾难$$$1$$$一天的开始,所有$$$k$$$法师都聚集在$$$1$$$岛上(他们试图关闭传送门,但发现这是不可能的)。在一天开始时$$$2$$$,一大群恶魔将从传送门中出现,占领岛屿$$$1$$$并杀死留在该岛上的所有法师。每天$$$i$$$中,如果岛屿$$$v$$$在一天开始时被恶魔占领,恶魔大军将穿越所有直接连接到$$$v$$$的桥梁,占领他们到达的每个岛屿,并杀死他们沿途遇到的每个法师。

每座桥都包含一块魔法石。每个法师在一天开始时都可以执行以下操作之一:

- 花一天时间沿着连接法师当前所在岛屿的桥梁之一旅行。过桥时,法师可以拾取桥上的魔法石(如果有的话,每块魔法石最多可以由一名法师拾取)。如果恶魔在当天或第二天开始时通过桥梁,法师所在的岛屿已经被恶魔部落占领(即使他们同时到达那里),法师就会被杀死。
- 进行一次传送仪式以到达达拉然郊外的安全地带。该仪式消耗两块魔法石(如果法师的魔法石少于两块则无法执行)。

每块魔法石会在$$$2$$$天内腐烂,因此如果在$$$i$$$的中间拾取,它会在$$$i$$$的中间腐烂。腐烂的石头不能用于传送仪式。

计算能够安全到达的法师的最大数量。

输入

第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$2 \le n \le 10^5$$$; $$$n - 1 \le m \le 10^5$$$; $$$1 \le k \le 10^5$$$) — 岛屿数量、桥梁数量和法师数量。

接下来是 $$$m$$$ 行,第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$) 表示岛屿 $$$x_i$$$ 和 $$$x_i$$$ 之间的桥梁$$$y_i$$$。

每对岛屿最多有一座桥梁连接它们。每个岛屿都可以沿着桥梁从其他岛屿到达。

输出

打印一个整数——能够安全到达的法师的最大数量。

示例

输入 #1

4 4 1
1 2
2 3
3 4
4 1

输出 #1

1

输入 #2

4 4 4
1 2
2 3
3 4
4 1

输出 #2

2

输入 #3

3 2 10
1 2
2 3

输出 #3

1

输入#4

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

输出#4

0