/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 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
入力例 1
5 4 1 5 2 1 2 5 4 3 1 5 1 3 3 4 1 3 4 5
出力例 1
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 2 1 2 2 1 1 2 1 2
出力例 2
No
条件を満たす P が存在しないので、No を出力します。
Score : 625 points
Problem Statement
You are given a directed graph with N vertices and M edges. For i = 1, 2, \ldots, M, the i-th edge is directed from vertex s_i to vertex t_i.
Determine whether there is a permutation P = (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N) that satisfies both of the following conditions, and if there is, provide an example.
- P_{s_i} \lt P_{t_i} for all i = 1, 2, \ldots, M.
- L_i \leq P_i \leq R_i for all i = 1, 2, \ldots, N.
Constraints
- 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
- All input values are integers.
Input
The input is given from Standard Input in the following format:
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
Output
If there is no P that satisfies the conditions, print No. If there is a P that satisfies the conditions, print Yes in the first line, and the elements of P separated by spaces in the second line, in the following format.
If multiple P's satisfy the conditions, any of them will be accepted.
Yes P_1 P_2 \ldots P_N
Sample Input 1
5 4 1 5 2 1 2 5 4 3 1 5 1 3 3 4 1 3 4 5
Sample Output 1
Yes 3 1 4 2 5
P = (3, 1, 4, 2, 5) satisfies the conditions. In fact,
- for the first edge (s_1, t_1) = (1, 5), we have P_1 = 3 \lt 5 = P_5;
- for the second edge (s_2, t_2) = (2, 1), we have P_2 = 1 \lt 3 = P_1;
- for the third edge (s_3, t_3) = (2, 5), we have P_2 = 1 \lt 5 = P_5;
- for the fourth edge (s_4, t_4) = (4, 3), we have P_4 = 2 \lt 4 = P_3.
Also,
- 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 Input 2
2 2 1 2 2 1 1 2 1 2
Sample Output 2
No
No P satisfies the conditions, so print No.