配点 : $625$ 点

問題文

$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$

制約

• $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$
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

$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

$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$

も成り立ちます。

2 2
1 2
2 1
1 2
1 2

No

条件を満たす $P$ が存在しないので、No を出力します。