Demonic Invasion
Contest: Kotlin Heroes: Episode 6
Difficulty rating: 3100
Tags: *special, flows

Dalaran 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 format:
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 format:
Print one integer — the maximum number of mages that can get to safety.

Constraints:
Time limit: 8.0 s
Memory limit: 512.0 MB

Example input:
4 4 1
1 2
2 3
3 4
4 1

Example output:
1

Example input:
4 4 4
1 2
2 3
3 4
4 1

Example output:
2

Editorial:
First of all, since mages are only one turn ahead of the horde, they must travel from node $$$1$$$ as far as possible, so let's construct the shortest path graph with BFS. The shortest path graph is constructed as follows: find the distances from $$$1$$$ to all other nodes, and for each edge from $$$x$$$ to $$$y$$$, add a directed arc from $$$x$$$ to $$$y$$$ if $$$d_x = d_y - 1$$$ (where $$$d_x$$$ is the distance from $$$1$$$ to $$$x$$$). Then, the mages should travel along the arcs of this directed acyclic graph.
Since each stone decays in $$$2$$$ days, a mage is able to perform a ritual only if they have taken two stones along two consecutive arcs in a path. Let's split all arcs into two parts: the ones leading from vertices with odd distances, and the ones leading from vertices with even distances. We can pair up two arcs from different parts if they share a vertex, so this problem can be reformulated as an instance of a bipartite maximum matching.
Unfortunately, even constructing this bipartite graph is quite costly (it may have up to $$$O(m^2)$$$ edges), let alone running Kuhn's algorithm on it. Let's try to design a flow solution. Let's add a source and a sink to our network (I call them $$$s$$$ and $$$t$$$ respectively). Split each arc by adding a new vertex $$$v$$$ and three arcs in our flow network:
• if the arc was going from the vertex $$$x$$$ with even distance to the vertex $$$y$$$ with odd distance, we add three arcs $$$(s, v)$$$, $$$(v, x)$$$ and $$$(v, y)$$$ (to model the fact that this arc can be paired with some other arc connected to $$$x$$$ or $$$y$$$);
• if the arc was going from the vertex $$$x$$$ with odd distance to the vertex $$$y$$$ with even distance, we add three arcs $$$(x, v)$$$, $$$(y, v)$$$ and $$$(v, t)$$$ (to model the same thing).
If the flow goes from $$$s$$$ to one of the vertices, it means that we have paired the respective arc (the same for the case when the flow goes from one of the vertices to $$$t$$$). So, the maximum flow $$$f$$$ in this network is the maximum number of pairs of arcs we can merge together. Thus, the answer to the problem is $$$\min(k, f)$$$.
The maximum flow can be computed in $$$O(m^{1.5})$$$ by using the Dinic algorithm since we have a unit network.