Boboniu Walks on Graph

Description:

Input:

The first line contains three integers $$$n$$$, $$$m$$$ and $$$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$$$).

Each of the next $$$m$$$ lines contains three integers $$$u$$$, $$$v$$$ and $$$w$$$ $$$(1\le u,v\le n,u\ne v,1\le w\le m)$$$, denoting an edge from $$$u$$$ to $$$v$$$ with weight $$$w$$$. It is guaranteed that there are no self-loops or multiple edges and each vertex has at least one edge starting from itself.

It is guaranteed that the out-degree of each vertex is at most $$$k$$$ and no two edges have equal weight.

Output:

Print one integer: the number of tuples.

Sample Input:

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

Sample Output:

2

Sample Input:

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

Sample Output:

1

Sample Input:

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

Sample Output:

1

Note:

For the first example, there are two tuples: $$$(1,1,3)$$$ and $$$(1,2,3)$$$. The blue edges in the picture denote the $$$c_i$$$-th smallest edges for each vertex, which Boboniu chooses to go through.

For the third example, there's only one tuple: $$$(1,2,2,2)$$$.

The out-degree of vertex $$$u$$$ means the number of edges outgoing from $$$u$$$.