Hints: https://atcoder.jp/contests/arc176/editorial/9845

For the sake of explanation, let’s construct beforehand a graph \(G\) with \(N\) vertices, where for each \(i\), an edge with weight \(C_i\) is spanned between vertices \(A_i\) and \(B_i\).

If \(\max(P_{A_i},P_{B_i}) = C_i\), then it is necessary that \(P_{A_i},P_{B_i} \le C_i\). Using this, for each \(i\), we derive a condition of the form \(P_i \le X_i\). (If vertex \(i\) is an isolated point in \(G\), then \(X_i = \infty\).)

We decide \(i\) for which \(P_i = k\) in the order of \(k = N,N-1,...,1\). During this, we perform the following case distinctions.

• If there are two or more instances of $i$ such that $C_i = k$
There can only be one $j$ such that $P_j = k$, so all edges with weight $k$ must have some vertex $v$ as an endpoint. Note here that if such a vertex $v$ exists, it is uniquely determined. If $v$ does not exist or $X_v < k$, the answer is immediately determined as $0$. Otherwise, we set $P_v = k$.
• If there is exactly one instance of $i$ such that $C_i = k$
Among the endpoints of that edge, we choose one such that $X_j \ge k$ and set $P_j = k$. If both endpoints meet the condition, the situation will be the same regardless of which we choose, so we multiply the answer by $2$ and set $P_j = k$ for either $j$. If neither endpoint meets the condition, the answer is immediately determined as $0$.
• If there is no instance of $i$ for which $C_i = k$
We choose one vertex from those such that $X_j \ge k$ and $P_j$ has not yet been decided, and set $P_j = k$. If no such vertex exists, the answer is immediately determined as $0$. If there are multiple such vertices, the situation will be the same regardless of which we choose, we multiply the answer by the number of candidates and set $P_j = k$ for some vertex.

By noting that \(P_{A_i}\) and \(P_{B_i}\) are not yet decided in the step \(k=C_i\) for \(i\) such that \(C_i = k\), and so on, it can be seen that the obtained permutation satisfies the conditions, and that all permutations satisfying the conditions are covered.

By managing the number of \(j\) such that \(X_j \ge k\) and \(P_j\) has not yet been decided while performing the above, this problem can be solved in \(\mathrm{O}(N + M)\).

Sample Implementation