[ABC304Ex] Constrained Topological Sort

给定一张 $n$ 个点 $m$ 条边的有向图，判断是否存在一个拓扑序 $P$ 满足 $P_i\in[L_i,R_i]$。 translated by cszyf

[problemUrl]: https://atcoder.jp/contests/abc304/tasks/abc304_h $ N $ 頂点 $ M $ 辺の有向グラフが与えられます。 $ i\ =\ 1,\ 2,\ \ldots,\ M $ について、$ i $ 番目の辺は頂点 $ s_i $ から頂点 $ t_i $ への有向辺です。 $ (1,\ 2,\ \ldots,\ N) $ の順列 $ P\ =\ (P_1,\ P_2,\ \ldots,\ P_N) $ であって下記の $ 2 $ つの条件をともに満たすものが存在するかを判定し、存在する場合はその一例を示してください。 - すべての $ i\ =\ 1,\ 2,\ \ldots,\ M $ について、$ P_{s_i}\ \lt\ P_{t_i} $ - すべての $ i\ =\ 1,\ 2,\ \ldots,\ N $ について、$ L_i\ \leq\ P_i\ \leq\ R_i $

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ s_1 $ $ t_1 $ $ s_2 $ $ t_2 $ $ \vdots $ $ s_M $ $ t_M $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ \vdots $ $ L_N $ $ R_N $

条件を満たす $ P $ が存在しない場合は、`No` と出力せよ。存在する場合は、下記の形式の通り、$ 1 $ 行目に `Yes` と出力し、 $ 2 $ 行目に $ P $ の各要素を空白区切りで出力せよ。 条件を満たす $ P $ が複数存在する場合は、そのうちのどれを出力しても正解となる。 > Yes $ P_1 $ $ P_2 $ $ \ldots $ $ P_N $

5 4
1 5
2 1
2 5
4 3
1 5
1 3
3 4
1 3
4 5

Yes
3 1 4 2 5

2 2
1 2
2 1
1 2
1 2

No

### 制約 - $ 2\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 0\ \leq\ M\ \leq\ \min\lbrace\ 4\ \times\ 10^5,\ N(N-1)\ \rbrace $ - $ 1\ \leq\ s_i,\ t_i\ \leq\ N $ - $ s_i\ \neq\ t_i $ - $ i\ \neq\ j\ \implies\ (s_i,\ t_i)\ \neq\ (s_j,\ t_j) $ - $ 1\ \leq\ L_i\ \leq\ R_i\ \leq\ N $ - 入力はすべて整数 ### Sample Explanation 1 $ P\ =\ (3,\ 1,\ 4,\ 2,\ 5) $ が条件を満たします。実際、 - $ 1 $ 番目の辺 $ (s_1,\ t_1)\ =\ (1,\ 5) $ について、$ P_1\ =\ 3\ \lt\ 5\ =\ P_5 $ - $ 2 $ 番目の辺 $ (s_2,\ t_2)\ =\ (2,\ 1) $ について、$ P_2\ =\ 1\ \lt\ 3\ =\ P_1 $ - $ 3 $ 番目の辺 $ (s_3,\ t_3)\ =\ (2,\ 5) $ について、$ P_2\ =\ 1\ \lt\ 5\ =\ P_5 $ - $ 4 $ 番目の辺 $ (s_4,\ t_4)\ =\ (4,\ 3) $ について、$ P_4\ =\ 2\ \lt\ 4\ =\ P_3 $ が成り立ちます。また、 - $ L_1\ =\ 1\ \leq\ P_1\ =\ 3\ \leq\ R_1\ =\ 5 $ - $ L_2\ =\ 1\ \leq\ P_2\ =\ 1\ \leq\ R_2\ =\ 3 $ - $ L_3\ =\ 3\ \leq\ P_3\ =\ 4\ \leq\ R_3\ =\ 4 $ - $ L_4\ =\ 1\ \leq\ P_4\ =\ 2\ \leq\ R_4\ =\ 3 $ - $ L_5\ =\ 4\ \leq\ P_5\ =\ 5\ \leq\ R_5\ =\ 5 $ も成り立ちます。 ### Sample Explanation 2 条件を満たす $ P $ が存在しないので、`No` を出力します。