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.

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.

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