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.

N/A

N/A

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