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$

### 限制条件 - $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 翻译