问题陈述

给定一个有$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$

示例输入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

没有满足条件的$P$，因此输出No。