\(N\) 頂点 \(M\) 辺のグラフであって、\(i\) 番目の辺が頂点 \(A_i\) と頂点 \(B_i\) を結ぶ辺であるようなものを考えます。

制約から、整数列 \(D = (D_1, D_2, \ldots, D_N)\) であって、各 \(i\) について \(D_{A_i} - D_{B_i} = C_i\) であるようなものを取ることができます。 この整数列は上で与えたグラフ上で適切に DFS や BFS などを行うことで得ることができます。

人 \(i\) の順位を \(X_i\) とすると、\(X = (X_1, X_2, \ldots, X_N)\) としてあり得る数列は \((1,2,\ldots, N)\) の並べ替えであって以下の条件を満たすもの、またそのようなものに限られます。

• 各連結成分ごとに適当な整数 \(v\) を選び、連結成分上の各頂点 \(i\) に対して \(X_i = D_i + v\) とする。

ここで、クエリを連結成分ごとに解くことを考えます。

\(i\) 番目のクエリの答えを求める際には、頂点 \(i\) を含まない連結成分を配置していく bit dp を行います。具体的には、\(dp_{x,y}\) を（頂点 \(i\) が含まれる連結成分を除き）\(x\) 番目までの連結成分の頂点に対応する順位の集合が \(y\) になる可能性があるかを表す bool 値として持てばよいです。

各連結成分ごとに順位の組としてあり得るものは \(O(N)\) 個しかないため、上の dp は素朴に時間計算量 \(O(N^22^N)\)、\(x\) の値から考えるべき \(y\) の popcount が \(1\) つに決まることを利用すると時間計算量 \(O(N2^N)\) で行えます。

よって全体として時間計算量 \(O(N^22^N)\) でこの問題を解くことができました。