CF730K Roads Orientation Problem

Berland 有 $n$ 个城市和 $m$ 条双向道路，每条道路连接两个城市。没有道路连接同一个城市，也没有两座城市间有多于一条道路。可以通过道路从任意一座城市到达其他任意一座城市。 现在总统先生位于城市 $s$，目的地是城市 $t$。他计划从 $s$ 沿着道路前往 $t$（$s\neq t$）。 因此，愚人和道路部正在度过艰难时光。部长担心总统先生可能会陷入交通堵塞或迷路。谁知道还会发生什么！ 为了确保一切按计划进行，部长决定临时将所有道路变为单向道路。也就是说，每条道路将被定向为两种可能的方向之一。必须满足以下条件： - 定向后，道路上不应存在环路。 - 城市 $s$ 应该是唯一一个所有道路都朝外定向的城市（即没有进入 $s$ 的道路，并且只有 $s$ 满足这个条件）。 - 城市 $t$ 应该是唯一一个所有道路都朝内定向的城市（即没有从 $t$ 出去的道路，并且只有 $t$ 满足这个条件）。 请帮助部长解决这个问题。写一个程序，找出一种满足要求的道路定向方法，或者报告无解。

本题包含多组测试用例。输入的第一行为正整数 $T$，表示需要解决的测试用例数量。 每个测试用例第一行包含四个整数 $n$、$m$、$s$ 和 $t$（$2 \leq n \leq 4 \cdot 10^{5}$，$1 \leq m \leq 10^{6}$，$1 \leq s,t \leq n$，$s \neq t$），分别表示城市数量、道路数量、出发城市和目的地城市编号。城市编号从 $1$ 到 $n$。 接下来的 $m$ 行，每行两个整数 $x_j$、$y_j$（$1 \leq x_j, y_j \leq n$，$x_j \neq y_j$），表示第 $j$ 条道路连接城市 $x_j$ 和 $y_j$。任意一对城市间最多有一条道路。可以通过道路从任意城市到达其他城市。 所有测试用例中 $n$ 的总和不超过 $4 \cdot 10^{5}$，所有测试用例中 $m$ 的总和不超过 $10^{6}$。

对于每个测试用例，如果有可行的道路定向方案，输出一行 “Yes”。接下来的 $m$ 行，每行输出一条道路的定向，格式为 $x\ y$，表示该道路从 $x$ 指向 $y$。道路可按任意顺序输出，如果有多种答案，输出任意一种。 如果无解，则仅输出一行 "No"。

由 ChatGPT 5 翻译