← 返回题目列表

AtCoder · abc304_h

Ex. 约束拓扑排序

中文机器翻译题面 查看原题

分数: 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.