← 返回题目列表

Codeforces · 1394/B

B. Boboniu 在图上行走

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

Boboniu 有一个有向图,其中有 $$$n$$$ 个顶点和 $$$m$$$ 个边。

每个顶点的出度最多为$$$k$$$。

每条边的权重介于 $$$1$$$ 和 $$$m$$$ 之间。没有两条边具有相同的权重。

Boboniu 喜欢在有一些特定规则的图上行走,这些规则由元组 $$$(c_1,c_2,\ldots,c_k)$$$ 表示。如果他现在站在出度为 $$$i$$$ 的顶点 $$$u$$$ 上,那么他将沿着从 $$$u$$$ 发出的所有边中权值最小的 $$$c_i$$$-th $$$(1\le c_i\le i)$$$ 到下一个顶点。

现在 Boboniu 要求您计算元组 $$$(c_1,c_2,\ldots,c_k)$$$ 的数量,使得

- $$$1\le c_i\le i$$$ 对于所有 $$$i$$$ ($$$1\le i\le k$$$)。
- 从任何顶点 $$$u$$$ 开始,通过在所描述的规则下在图上行走,可以在有限时间内返回到 $$$u$$$。

输入

第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$2\le n\le 2\cdot 10^5$$$、$$$2\le m\le \min(2\cdot 10^5,n(n-1) )$$$、$$$1\le k\le 9$$$)。

接下来的 $$$m$$$ 行包含三个整数 $$$u$$$、$$$v$$$ 和 $$$w$$$ $$$(1\le u,v\le n,u\ne v,1\le w\le m)$$$,表示从 $$$u$$$ 到 $$$v$$$ 的边,权重为 $$$w$$$。保证不存在自环或多条边,并且每个顶点至少有一条从自身开始的边。

保证每个顶点的出度至多为$$$k$$$,并且没有两条边具有相等的权重。

输出

打印一个整数:元组的数量。

示例

输入 #1

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

输出 #1

2

输入 #2

5 5 1
1 4 1
5 1 2
2 5 3
4 3 4
3 2 5

输出 #2

1

输入 #3

6 13 4
3 5 1
2 5 2
6 3 3
1 4 4
2 6 5
5 3 6
4 1 7
4 3 8
5 2 9
4 2 10
2 1 11
6 1 12
4 6 13

输出 #3

1

注意

对于第一个示例,有两个元组:$$$(1,1,3)$$$ 和 $$$(1,2,3)$$$。图片中的蓝色边表示每个顶点的第 $$$c_i$$$ 个最小边,Boboniu 选择经过这些边。

对于第三个示例,只有一个元组:$$$(1,2,2,2)$$$。

顶点$$$u$$$的出度表示从$$$u$$$出的边的条数。