叛军在最近与帝国军队的战斗中被镇压,但仍有一线新的希望。
与此同时,在一颗被征服的行星上,卢克正在准备一场非法的街头比赛(考虑到他的家族历史,这应该不足为奇)。卢克以 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$$$ 行星的单独飞船。