The following languages are only available languages for the problems from the contest

Kotlin Heroes: Episode 6:

- Kotlin 1.4.31

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
I. Demonic Invasion

time limit per test

8 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputDalaran is a flying city of magic. It consists of $$$n$$$ floating islands connected by $$$m$$$ bridges (each bridge can be traversed in both directions). Every island is reachable from every other along these bridges. It would be a shame if some magic experiment went horribly wrong and this magnificent city got destroyed, right?

Well, just guess what happened. A portal to demons' realm was opened at the island $$$1$$$. This is the start of day $$$1$$$ of the catastrophe, and all $$$k$$$ mages have gathered at the island $$$1$$$ (they were trying to close the portal, but found out that it was impossible). At the start of day $$$2$$$, a gigantic horde of demons will emerge from the portal, capture the island $$$1$$$ and kill every mage staying at that island. During each day $$$i$$$, if the island $$$v$$$ was captured by demons by the start of the day, the horde of demons will travel across all bridges connected directly to $$$v$$$, capture every island they reach, and kill every mage they meet along the way.

Each bridge contains exactly one magic stone. Each mage at the start of the day can do one of the following actions:

- Spend one day travelling along one of the bridges connected to the island where the mage currently is. When passing through a bridge, the mage can pick up the magic stone from it (if there is any; each magic stone can be picked up by at most one mage). If the bridge is passed by the demons during the same day, or by the start of the next day, the island where the mage goes is already captured by the demonic horde (even if they arrive there at the same moment), the mage is killed.
- Perform a teleportation ritual to get to safety outside Dalaran. This ritual consumes two magic stones (and cannot be performed if the mage has less than two stones).

Each magic stone decays in $$$2$$$ days, so if is picked up in the middle of day $$$i$$$, it decays in the middle of day $$$i + 2$$$. Decayed stones cannot be used in teleportation ritual.

Calculate the maximum number of mages that can get to safety.

Input

The first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$2 \le n \le 10^5$$$; $$$n - 1 \le m \le 10^5$$$; $$$1 \le k \le 10^5$$$) — the number of islands, the number of bridges and the number of mages.

Then $$$m$$$ lines follow, the $$$i$$$-th line contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$) denoting a bridge between the islands $$$x_i$$$ and $$$y_i$$$.

Each pair of islands has at most one bridge connecting them. Every island is reachable from every other island along the bridges.

Output

Print one integer — the maximum number of mages that can get to safety.

Examples

Input

4 4 1 1 2 2 3 3 4 4 1

Output

1

Input

4 4 4 1 2 2 3 3 4 4 1

Output

2

Input

3 2 10 1 2 2 3

Output

1

Input

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

Output

0

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/17/2022 17:37:52 (k2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|