CF1835D Doctor's Brown Hypothesis

在与帝国军队的最近一场战斗中，反叛军被彻底击溃，但仍有一线新的希望。 与此同时，在被征服的某颗星球上，Luke 正在准备一场非法街头赛车（鉴于他的家族历史，这并不令人意外）。Luke 以每小时 88 英里的速度到达终点线。下车后，他发现自己来到了一个新的现实。原来，战斗尚未发生，将在恰好 $k$ 小时后开始。 反叛军在 $n$ 个星球中的每一个都部署了一艘战舰。$m$ 条单向虫洞连接着这些星球。通过每条虫洞都恰好需要一小时。帝国的将军们精确地制定了战斗计划，但他们的部队无法动态适应变化的局势。因此，反叛军只需在战斗开始前调动一些战舰，就能迷惑敌人，确保胜利，改变银河的命运。 由于各种战略考量（此处略去），反叛军希望选择两艘战舰互换位置，使得它们都能在整个时间内（恰好 $k$ 小时）一直移动。换句话说，反叛军需要找到两个星球 $x$ 和 $y$，使得存在长度为 $k$ 的路径从 $x$ 到 $y$，也存在长度为 $k$ 的路径从 $y$ 到 $x$。 由于燃料有限，只选择一艘战舰也是可以接受的。这艘战舰应当在虫洞中飞行 $k$ 小时后返回其初始星球。 请问有多少种方式可以选择战舰来完成任务？

输入的第一行包含三个整数 $n$、$m$ 和 $k$（$1 \leq n \leq 10^5$，$0 \leq m \leq 2 \times 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 \ne x_2$，要么 $y_1 \ne y_2$。

输出仅一行，表示可以选择战舰完成任务的方案数。

在第一个样例测试中，可以选择以下星球的战舰对：$2$ 和 $5$，$3$ 和 $5$，$1$ 和 $4$。也可以单独选择来自星球 $6$ 和 $7$ 的战舰。 在第二个样例测试中，可以选择以下星球的战舰对：$2$ 和 $3$。也可以单独选择来自星球 $1$、$2$、$3$、$4$ 和 $5$ 的战舰。 在第三个样例测试中，没有可以选择的战舰对。可以单独选择来自星球 $2$ 和 $3$ 的战舰。 由 ChatGPT 4.1 翻译