\(N\) 頂点のグラフを用意し、各 \((A_i, B_i)\) について頂点 \(A_i,B_i\) 間に辺を張ります。このグラフにおいて、各連結成分に書かれる数はすべて等しい必要があります。\(X_i=X_j\) となるべき \((i,j)\) をこのグラフを用いて一つにまとめることで、\((A_i,B_i)\) の制約がない場合の問題に帰着できます。

\(X_1.X_2,\ldots,X_N\) の順に決めます。\(X_i\) の値を決めることを考えます。このとき、\(S\coloneqq\lbrace X_j\mid D_j=i\rbrace\) とすると、\(X_i\) として採用できる数は \(S\) に含まれない正整数です。\(X\) を辞書順最小にするにあたり、\(X_i\) の値は \(S\) に含まれない最小の正整数にすれば良いです。

集合 \(S\) が与えられたときに \(S\) に含まれない最小の正整数は \(O(|S|)\) 時間で計算可能です。したがって、適切に実装すればこの問題は \(O(N+P+Q)\) 時間で解くことができます。