CF1394B.Boboniu Walks on Graph

Boboniu has a directed graph with $n$ vertices and $m$ edges.

The out-degree of each vertex is at most $k$.

Each edge has an integer weight between $1$ and $m$. No two edges have equal weights.

Boboniu likes to walk on the graph with some specific rules, which is represented by a tuple $(c_1,c_2,\ldots,c_k)$. If he now stands on a vertex $u$ with out-degree $i$, then he will go to the next vertex by the edge with the $c_i$-th $(1\le c_i\le i)$ smallest weight among all edges outgoing from $u$.

Now Boboniu asks you to calculate the number of tuples $(c_1,c_2,\ldots,c_k)$ such that

• $1\le c_i\le i$ for all $i$ ($1\le i\le k$).
• Starting from any vertex $u$, it is possible to go back to $u$ in finite time by walking on the graph under the described rules.

Boboniu 有一个包含 $n$ 个顶点和 $m$ 条边的有向图。

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

每条边具有一个介于 $1$ 和 $m$ 之间的整数权重。任意两条边的权重互不相同。

Boboniu 喜欢按照某些特定规则在图上行走，这些规则由一个元组 $(c_1,c_2,\ldots,c_k)$ 表示。若他当前位于出度为 $i$ 的顶点 $u$ 上，则他将沿着从 $u$ 出发的所有出边中权重第 $c_i$ 小（$1\le c_i\le i$）的那条边走向下一个顶点。

现在 Boboniu 要求你计算满足以下条件的元组 $(c_1,c_2,\ldots,c_k)$ 的数量：

• 对所有 $i$（$1\le i\le k$），均有 $1\le c_i\le i$；
• 从任意顶点 $u$ 出发，按照上述规则在图上行走，均能在有限步内返回 $u$。

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.

第一行包含三个整数 $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$，且任意两条边的权重互不相等。

Print one integer: the number of tuples.

输出一个整数：满足条件的元组个数。

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$.

对于第一个样例，存在两个三元组：$(1,1,3)$ 和 $(1,2,3)$。图中蓝色边表示每个顶点所选择的第 $c_i$ 小的边（即 Boboniu 选择经过的边）。

对于第三个样例，仅存在一个四元组：$(1,2,2,2)$。

顶点 $u$ 的出度指从 $u$ 出发的有向边的数量。