分数: 625 点
问题陈述
给你一个有向图 N 顶点和 M 边缘。 对于 i = 1, 2, \ldots, M, i第一条边从顶点定向 s_i 到顶点 t_i.
判断是否存在排列 P = (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N) 满足以下两个条件,如果有,请提供示例。
- P_{s_i} \lt P_{t_i} 对于所有人 i = 1, 2, \ldots, M.
- L_i \leq P_i \leq R_i 对于所有人 i = 1, 2, \ldots, N.
约束
- 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。如果有一个 P 满足条件,打印 Yes 在第一行,以及元素 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) 满足条件。事实上,
- 为第一个边缘 (s_1, t_1) = (1, 5),我们有 P_1 = 3 \lt 5 = P_5;
- 第二条边 (s_2, t_2) = (2, 1),我们有 P_2 = 1 \lt 3 = P_1;
- 为第三个边缘 (s_3, t_3) = (2, 5),我们有 P_2 = 1 \lt 5 = P_5;
- 为第四条边 (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
No P 满足条件,所以打印 No.