← 返回题目列表

Codeforces · 1835/D

D. 医生的布朗假设

中文机器翻译题面 查看原题

叛军在最近与帝国军队的战斗中被镇压,但仍有一线新的希望。

与此同时,在一颗被征服的行星上,卢克正在准备一场非法的街头比赛(考虑到他的家族历史,这应该不足为奇)。卢克以 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$$$ 有一个虫洞。保证不存在两个相同的虫洞,即。 e.对于每两个虫洞,$$$x_1 \neq x_2$$$ 或 $$$y_1 \neq y_2$$$。

输出

在第一行也是唯一一行中,您的程序应该输出为任务选择一对或单艘战舰的可能方法的数量。

示例

输入 #1

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

输出 #1

5

输入 #2

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

输出 #2

6

输入 #3

3 3 30
1 2
2 3
3 2

输出 #3

2

注意

在第一个样本测试中,可以从以下行星中选择成对的飞船:$$$2$$$ 和 $$$5$$$、$$$3$$$ 和 $$$5$$$、$$$1$$$ 和 $$$4$$$。也可以选择来自 $$$6$$$ 和 $$$7$$$ 行星的单独飞船。

在第二个样本测试中,可以从以下行星中选择一对飞船:$$$2$$$ 和 $$$3$$$。还可以选择来自行星 $$$1$$$、$$$2$$$、$$$3$$$、$$$4$$$ 和 $$$5$$$ 的单独飞船。

在第三次样本测试中,我们没有可供选择的成对船舶。也可以选择来自 $$$2$$$ 和 $$$3$$$ 行星的单独飞船。