
ZOJ Problem Set  3874
Edward has a permutation {a_{1}, a_{2}, … a_{n}}. He finds that if he connects each pair (a_{i}, a_{j}) such that i < j and a_{i} > a_{j}, he will get a graph. For example, if the permutation is {2, 3, 1, 4}, then 1 and 2 are connected and 1 and 3 are connected. Edward lost his permutation, but he does know the connected components of the corresponding graph. He wants to know how many permutations will result in the same connected components. Note that two vertices u, v belong to the same connected component if there exists a sequence of vertices starting with u and ending with v such that every two subsequent vertices in the sequence are connected by an edge. InputThere are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case: The first line contains two integers n, m (1 ≤ m ≤ n ≤ 100000), indicating the length of the permutation and the number of connected components in the graph. Each of the following m lines contains an integer c_{i} which denotes the size of ith connected component, followed by c_{i} distinct integers v_{i,1}, v_{i,2}, … v_{i,ci} which denotes the connected component (1 ≤ c_{i}, v_{i,1}, v_{i,2}, … v_{i,ci} ≤ n). It is guaranteed that every number will appear in exact one connected component and c_{1} + c_{2} + … + c_{m} = n. OutputFor each case, output the answer modulo 786433. Sample Input2 4 4 1 1 1 2 1 3 1 4 4 2 3 1 2 3 1 4 Sample Output1 3 HintFor the second case, the three permutations is: {2, 3, 1, 4}, {3, 2, 1, 4}, {3, 1, 2, 4}. Author: LIN, Xi Source: The 12th Zhejiang Provincial Collegiate Programming Contest 