AT_abc304_h [ABC304Ex] Constrained Topological Sort

题目描述

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

请判断是否存在一个 $N$ 元的排列 $P=(P_1,P_2,\ldots,P_N)$，满足以下两个条件，并在存在时给出一个例子：

• 对于所有 $i=1,2,\ldots,M$，都有 $P_{s_i} < P_{t_i}$。
• 对于所有 $i=1,2,\ldots,N$，都有 $L_i \leq P_i \leq R_i$。

输入格式

输入以如下格式从标准输入读入。

$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。如果存在，第一行输出 Yes，第二行输出 $P$ 的每个元素，空格分隔。如果有多个满足条件的 $P$，输出其中任意一个均可。

Yes
$P_1$ $P_2$ $\ldots$ $P_N$

输入输出样例 #1

输入 #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

输入输出样例 #2

输入 #2

2 2
1 2
2 1
1 2
1 2

输出 #2

No

说明/提示

限制条件

• $2 \leq N \leq 2 \times 10^5$
• $0 \leq M \leq \min\{4 \times 10^5, N(N-1)\}$
• $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$
• 输入均为整数

样例解释 1

$P=(3,1,4,2,5)$ 满足条件。实际上，

• 第 1 条边 $(s_1, t_1) = (1, 5)$，有 $P_1=3 < 5=P_5$
• 第 2 条边 $(s_2, t_2) = (2, 1)$，有 $P_2=1 < 3=P_1$
• 第 3 条边 $(s_3, t_3) = (2, 5)$，有 $P_2=1 < 5=P_5$
• 第 4 条边 $(s_4, t_4) = (4, 3)$，有 $P_4=2 < 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

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

由 ChatGPT 4.1 翻译