Doctor's Brown Hypothesis
Contest: Codeforces Round 880 (Div. 1)
Difficulty rating: 2900
Tags: dfs and similar, graphs, math, number theory

The rebels have been crushed in the most recent battle with the imperial forces, but there is a ray of new hope.

Meanwhile, on one of the conquered planets, Luke was getting ready for an illegal street race (which should come as no surprise, given his family history). Luke arrived at the finish line with 88 miles per hour on his speedometer. After getting out of the car, he was greeted by a new reality. It turns out that the battle has not happened yet and will start in exactly $$$k$$$ hours.

The rebels have placed a single battleship on each of the $$$n$$$ planets. $$$m$$$ unidirectional wormholes connect the planets. Traversing each wormhole takes exactly one hour. Generals of the Imperium have planned the battle precisely, but their troops cannot dynamically adapt to changing circumstances. Because of this, it is enough for the rebels to move some ships around before the battle to confuse the enemy, secure victory and change the galaxy's fate.

Owing to numerous strategical considerations, which we now omit, the rebels would like to choose two ships that will switch places so that both of them will be on the move for the whole time (exactly $$$k$$$ hours). In other words, rebels look for two planets, $$$x$$$ and $$$y$$$, such that paths of length $$$k$$$ exist from $$$x$$$ to $$$y$$$ and from $$$y$$$ to $$$x$$$.

Because of the limited fuel supply, choosing one ship would also be acceptable. This ship should fly through the wormholes for $$$k$$$ hours and then return to its initial planet.

How many ways are there to choose the ships for completing the mission?

Input format:
In the first line of input, there are three integer numbers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \leq n \leq 10^5$$$, $$$0 \leq m \leq 2 \cdot 10^5$$$, $$$n^3 \leq k \leq 10^{18}$$$) denoting respectively the number of planets, wormholes and hours left until the battle starts.

The following $$$m$$$ lines contain two integers each, $$$x$$$ and $$$y$$$ ($$$1 \leq x, y \leq n$$$, $$$x \ne y$$$), meaning that there is a wormhole from planet $$$x$$$ to planet $$$y$$$. It is guaranteed that there are no two identical wormholes, i. e. for every two wormholes, either $$$x_1 \neq x_2$$$ or $$$y_1 \neq y_2$$$.

Output format:
In the first and only line, your program should output the number of possible ways of choosing a pair or a single warship for the mission.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first sample test, one can choose pairs of ships from the following planets: $$$2$$$ and $$$5$$$, $$$3$$$ and $$$5$$$, $$$1$$$ and $$$4$$$. Individual ships from planets $$$6$$$ and $$$7$$$ could also be chosen.

In the second sample test, one can choose a pair of ships from the following planets: $$$2$$$ and $$$3$$$. Individual ships from planets $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, and $$$5$$$ could also be chosen.

In the third sample test, there are no pairs of ships we can choose. Individual ships from planets $$$2$$$ and $$$3$$$ could also be chosen.

Example input:
7 8 346
1 2
1 3
2 4
3 4
4 5
5 1
6 7
7 6

Example output:
5

Example input:
5 6 128
1 2
1 3
2 4
3 4
4 5
5 1

Example output:
6

Editorial:
As both vertices must visit each other, they must be in the same strongly connected component. We can compute all SCC and solve for them independently. Further, we will assume that we are solving for a fixed SCC.
The critical observation is that $$$n^3$$$ is enormous, and we can visit an entire graph. This gives us hope that if we fix a vertex $$$v$$$, we can represent all vertices that are reachable from it.
If we compute the greatest common divisor of all cycles in our graph $$$g$$$, then all paths from a fixed vertex $$$s$$$ to a vertex $$$t$$$ have the same remainder modulo $$$g$$$. Moreover, we can always find such if we are looking for a long enough path and the correct remainder. It turns out that $$$n^3$$$ is a large enough bound for such paths.
Now we have to find the greatest common divisor of all cycles in the graph. There are many ways (including linear), but we are going to present $$$\mathcal{O}(n \log n)$$$ here. First, find any cycle in the graph. As $$$g$$$ has to divide it, we just have to consider its divisors.
We'll develop a quick way to find if a divisor $$$d$$$ divides $$$g$$$. To do this, we check if there is a colouring with colours from $$$0$$$ to $$$d - 1$$$, such that for every edge $$$\langle u, v \rangle$$$, $$$ colour (v) = (colour (u) + 1) \mod d$$$. We can check for such colouring with a simple DFS in a linear time.
To obtain the right complexity, we'll only check prime divisors (and their powers, and take the least common multiple of the ones which divide $$$g$$$.
Now we have to find all pairs $$$\langle s, t \rangle$$$ such that there are paths from $$$s$$$ to $$$t$$$ and from $$$t$$$ to $$$s$$$ of length $$$k$$$. We have two cases. Either $$$g | k$$$ and $$$colour(s) = colour(t)$$$ or $$$2 | g$$$ and $$$k = g / 2 \mod g$$$ and $$$colour(s) = (colour(t) + g / 2) \mod g$$$. After preprocessing, we can check both cases in $$$\mathcal{O}(g)$$$ time.
The final complexity is $$$\mathcal{O}(n \log n)$$$ or $$$\mathcal{O}(n)$$$ depending on the implementation.