Berland由n个城市和m条连接城市的双向道路组成。没有一条道路将一座城市与其自身连接起来,并且在任何一对城市之间也只有一条道路。从任何其他沿着道路行驶的地方都可以到达任何城市。
目前总统先生在城市s,他的目的地是城市t。他计划沿着道路从 s 移动到 t (s ≠ t)。
这就是愚路部日子不好过的原因。部长担心总统先生可能会遇到交通堵塞或迷路。谁知道还会发生什么!
为了确保一切按计划进行,部长决定暂时将所有道路设为单向。因此,每条道路都将朝向两个可能的方向之一。必须满足以下条件:
- 定向后道路上不应有自行车。
- 城市 s 应该是唯一一个其所有道路都向外延伸的城市(即没有通往城市 s 的传入道路,并且城市 s 是唯一这样的城市)。
- 城市 t 应该是唯一一个其所有道路都面向的城市(即没有从城市 t 出去的道路,并且城市 t 是唯一这样的城市)。
帮助部长解决他的问题。编写一个程序来查找所有道路的任何此类方向或报告不存在解决方案。
输入
此问题中的每个测试都包含一个或多个要解决的测试用例。输入的第一行包含正数 T — 要解决的案例数。
每个案例都以包含四个整数 n、m、s 和 t 的行开始 (2 ≤ n ≤ 4·105, 1 ≤ m ≤ 106, 1 ≤ s, t ≤ n, s ≠ t) — 城市数量、道路数量以及出发和目的地城市的索引。城市编号为 1 到 n。
以下 m 行包含道路,每行一条道路。每条道路都由两个整数 xj, yj (1 ≤ xj, yj ≤ n, xj ≠ yj) 给出,这意味着第 j 条道路连接城市 xj 和 yj。任意一对城市之间至多有一条道路。从任何其他沿着道路行驶的地方都可以到达任何城市。
测试中所有案例的 n 值总和不超过 4·105。测试中所有案例的值 m 之和不超过 106。
输出
对于每种情况,如果答案存在,请打印“是”。在接下来的 m 行中打印所需方向的道路。您可以按任意顺序打印道路。如果有多个答案,请打印其中任何一个。
如果案例没有答案,则打印唯一一行“否”。
示例
输入 #1
2 4 4 1 2 1 2 2 3 3 4 4 1 3 2 1 3 3 1 2 3
输出 #1
Yes 1 2 3 2 4 3 1 4 No