Consider a \(N\)-vertex \(M\)-edge graph whose \(i\)-th edge connects vertex \(A_i\) and vertex \(B_i\).

By the constraints, we can take an integer sequence \(D = (D_1, D_2, \ldots, D_N)\) such that \(D_{A_i} - D_{B_i} = C_i\) for each \(i\). This sequence can be obtained by appropriately performing DFS (Depth-First Search) or BFS (Breadth-First Search) on the graph defined above.

The sequence of person \(i\)’s rank \(X_i\), collectively written as \(X = (X_1, X_2, \ldots, X_N)\), is limited to permutations of \((1,2,\ldots, N)\) such that:

• \(X_i = D_i + v\), where \(v\) is an arbitrary integer taken for each connected component and \(i\) is any of the vertex in it.

We try to respond to the query per connected component.

When finding the answer to the \(i\)-th query, we perform a bit DP (Dynamic Programming) that places connected components not containing vertex \(i\). Specifically, maintain boolean values \(dp_{x,y}\) that represent whether the vertices in the first \(x\) connected components may correspond to the set of ranks \(y\).

Since there are \(O(N)\) pairs of possible tuples of rank for each connected component, the DP above costs \(O(N^22^N)\) time naively, or \(O(N2^N)\) time if you use the property that the value of \(x\) uniquely determines the popcount of \(y\).

Therefore, the problem has been solved in a total of \(O(N^22^N)\) time.