当前没有测试数据。

有限拓扑排序

得分：$625$ 分

问题描述

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

判断是否存在一个排列 $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 \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。如果存在满足条件的 $P$，则第一行输出 Yes，第二行输出用空格分隔的 $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)$ 满足条件。事实上，

• 对于第一条边 $(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
1 2
2 1
1 2
1 2

No

没有满足条件的 $P$，所以输出 No。