受限拓扑排序

题目描述

给你一个具有 $N$ 个顶点和 $M$ 条边的有向图。 对于 $i = 1, 2, \ldots, M$,第 $i$ 条边是从顶点 $s_i$ 指向顶点 $t_i$ 的有向边。

请判断是否存在一个 $(1, 2, \ldots, N)$ 的排列 $P = (P_1, P_2, \ldots, P_N)$ 同时满足以下两个条件,如果存在,请给出一个例子。

• 对所有 $i = 1, 2, \ldots, M$,有 $P_{s_i} \lt P_{t_i}$。
• 对所有 $i = 1, 2, \ldots, N$,有 $L_i \le P_i \le R_i$。

输入格式

输入按以下格式从标准输入给出:

N M
s_1 t_1
s_2 t_2
⋮
s_M t_M
L_1 R_1
L_2 R_2
⋮
L_N R_N

输出格式

如果不存在满足条件的 $P$,输出 No。如果存在满足条件的 $P$,在第一行输出 Yes,在第二行以空格分隔输出 $P$ 的元素,格式如下。 如果存在多个满足条件的 $P$,任意一个都会被接受。

Yes
P_1 P_2 … 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)$ 满足条件。事实上,

对于第一条边 $(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 \le P_1 = 3 \le R_1 = 5$,

$L_2 = 1 \le P_2 = 1 \le R_2 = 3$,

$L_3 = 3 \le P_3 = 4 \le R_3 = 4$,

$L_4 = 1 \le P_4 = 2 \le R_4 = 3$,

$L_5 = 4 \le P_5 = 5 \le R_5 = 5$。

2 2
1 2
2 1
1 2
1 2

No

不存在满足条件的 $P$,因此输出 No。

数据范围

• $2 \le N \le 2 \times 10^5$
• $0 \le M \le \min\lbrace 4 \times 10^5, N(N-1) \rbrace$
• $1 \le s_i, t_i \le N$
• $s_i \neq t_i$
• 当 $i \neq j$ 时,$(s_i, t_i) \neq (s_j, t_j)$
• $1 \le L_i \le R_i \le N$
• 所有输入值均为整数。

提示

答案不唯一,输出任意合法解即可。