达拉然是一座飞行的魔法之城。它由 $$$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