310450: CF1835D. Doctor's Brown Hypothesis

D. Doctor's Brown Hypothesistime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

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

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.

ExamplesInput

7 8 346
1 2
1 3
2 4
3 4
4 5
5 1
6 7
7 6

Output

5

Input

5 6 128
1 2
1 3
2 4
3 4
4 5
5 1

Output

6

Input

3 3 30
1 2
2 3
3 2

Output

2

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.

题目大意：
帝国军队在最近的战斗中击败了叛军，但新的希望出现了。在其中一个被征服的星球上，卢克准备参加一场非法街头赛车。卢克以每小时88英里的速度到达终点线，下车后，他遇到了一个新现实。战斗其实还没有发生，将在确切地$$k$$小时后开始。叛军在每一个星球上都部署了一艘战舰，共有$$n$$个星球。$$m$$个单向虫洞连接着这些星球，穿越每个虫洞需要正好一个小时。帝国将军们精确地计划了战斗，但他们的部队不能动态适应变化的情况。因此，叛军只需在战斗前移动一些飞船，就能迷惑敌人，确保胜利，改变银河系的命运。叛军希望选择两艘飞船交换位置，以便它们在整个时间（正好$$k$$小时）都在移动。也就是说，叛军寻找两个星球$$x$$和$$y$$，从$$x$$到$$y$$和从$$y$$到$$x$$都存在长度为$$k$$的路径。由于燃料有限，选择一艘飞船也是可以接受的。这艘飞船应该飞行$$k$$小时，然后返回其初始星球。问题是：完成任务的飞船选择方式有多少种？

输入输出数据格式：
输入：
第一行包含三个整数$$n$$、$$m$$和$$k$$，分别表示行星的数量、虫洞的数量和战斗开始前的小时数（$$1 \leq n \leq 10^5$$，$$0 \leq m \leq 2 \cdot 10^5$$，$$n^3 \leq k \leq 10^{18}$$）。
接下来$$m$$行，每行包含两个整数$$x$$和$$y$$（$$1 \leq x, y \leq n$$，$$x \ne y$$），表示存在一个从行星$$x$$到行星$$y$$的虫洞。保证没有两个相同的虫洞，即对于任意两个虫洞，要么$$x_1 \neq x_2$$要么$$y_1 \neq y_2$$。

输出：
程序应输出第一行，内容是选择一对或单个战舰完成任务的可能方式数量。

示例：
输入：
```
7 8 346
1 2
1 3
2 4
3 4
4 5
5 1
6 7
7 6
```
输出：
```
5
```
解释：
在这个例子中，可以选择以下行星对的战舰：$$2$$和$$5$$，$$3$$和$$5$$，$$1$$和$$4$$。也可以选择单个战舰来自行星$$6$$和$$7$$。题目大意： 帝国军队在最近的战斗中击败了叛军，但新的希望出现了。在其中一个被征服的星球上，卢克准备参加一场非法街头赛车。卢克以每小时88英里的速度到达终点线，下车后，他遇到了一个新现实。战斗其实还没有发生，将在确切地$$k$$小时后开始。叛军在每一个星球上都部署了一艘战舰，共有$$n$$个星球。$$m$$个单向虫洞连接着这些星球，穿越每个虫洞需要正好一个小时。帝国将军们精确地计划了战斗，但他们的部队不能动态适应变化的情况。因此，叛军只需在战斗前移动一些飞船，就能迷惑敌人，确保胜利，改变银河系的命运。叛军希望选择两艘飞船交换位置，以便它们在整个时间（正好$$k$$小时）都在移动。也就是说，叛军寻找两个星球$$x$$和$$y$$，从$$x$$到$$y$$和从$$y$$到$$x$$都存在长度为$$k$$的路径。由于燃料有限，选择一艘飞船也是可以接受的。这艘飞船应该飞行$$k$$小时，然后返回其初始星球。问题是：完成任务的飞船选择方式有多少种？ 输入输出数据格式： 输入： 第一行包含三个整数$$n$$、$$m$$和$$k$$，分别表示行星的数量、虫洞的数量和战斗开始前的小时数（$$1 \leq n \leq 10^5$$，$$0 \leq m \leq 2 \cdot 10^5$$，$$n^3 \leq k \leq 10^{18}$$）。 接下来$$m$$行，每行包含两个整数$$x$$和$$y$$（$$1 \leq x, y \leq n$$，$$x \ne y$$），表示存在一个从行星$$x$$到行星$$y$$的虫洞。保证没有两个相同的虫洞，即对于任意两个虫洞，要么$$x_1 \neq x_2$$要么$$y_1 \neq y_2$$。 输出： 程序应输出第一行，内容是选择一对或单个战舰完成任务的可能方式数量。 示例： 输入： ``` 7 8 346 1 2 1 3 2 4 3 4 4 5 5 1 6 7 7 6 ``` 输出： ``` 5 ``` 解释： 在这个例子中，可以选择以下行星对的战舰：$$2$$和$$5$$，$$3$$和$$5$$，$$1$$和$$4$$。也可以选择单个战舰来自行星$$6$$和$$7$$。