CF1835D.Doctor's Brown Hypothesis

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?

叛军在最近一次与帝国军队的战斗中被彻底击溃，但新的希望之光已然浮现。

与此同时，在一颗已被征服的星球上，卢克正准备参加一场非法街头赛车（鉴于他的家族历史，这并不令人意外）。卢克以时速 88 英里抵达终点线。当他下车后，却迎来了一番全新的现实：原来那场战役尚未发生，且将在恰好 $k$ 小时后打响。

叛军已在全部 $n$ 颗星球上各部署了一艘战舰。共有 $m$ 条单向虫洞连接这些星球，穿越每条虫洞恰好耗时一小时。帝国将军们虽已对战役进行了精确筹划，但其部队无法根据变化的形势动态调整。正因如此，叛军只需在战役开始前将部分战舰重新部署，即可迷惑敌军、确保胜利，并改变银河系的命运。

出于诸多战略考量（此处略去细节），叛军希望选出两艘战舰，使其互换位置，且两艘战舰在整个过程中均处于持续航行状态（即航行时间恰好为 $k$ 小时）。换言之，叛军需寻找两颗星球 $x$ 和 $y$，使得存在长度为 $k$ 的路径从 $x$ 到 $y$，同时也存在长度为 $k$ 的路径从 $y$ 到 $x$。

由于燃料供应有限，仅选择一艘战舰亦可接受。该战舰需经由虫洞连续飞行 $k$ 小时，随后返回其初始星球。

完成此次任务，共有多少种选择战舰的方式？

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$.

输入的第一行包含三个整数 $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$。

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.

在第一行且唯一的一行中，你的程序应输出为执行任务而选择一对或一艘战舰的可能方案数。

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.

在第一个样例测试中，可以选择来自以下行星的飞船对：$2$ 和 $5$、$3$ 和 $5$、$1$ 和 $4$。此外，也可以单独选择来自行星 $6$ 和 $7$ 的飞船。

在第二个样例测试中，可以选择来自以下行星的飞船对：$2$ 和 $3$。此外，也可以单独选择来自行星 $1$、$2$、$3$、$4$ 和 $5$ 的飞船。

在第三个样例测试中，不存在可选的飞船对。此外，也可以单独选择来自行星 $2$ 和 $3$ 的飞船。