CF730K.Roads Orientation Problem

Berland consists of n cities and m bidirectional roads connecting pairs of cities. There is no road connecting a city to itself, and between any pair of cities there is no more than one road. It is possible to reach any city from any other moving along roads.

Currently Mr. President is in the city s and his destination is the city t. He plans to move along roads from s to t (s ≠ t).

That's why Ministry of Fools and Roads has difficult days. The minister is afraid that Mr. President could get into a traffic jam or get lost. Who knows what else can happen!

To be sure that everything goes as planned, the minister decided to temporarily make all roads one-way. So each road will be oriented in one of two possible directions. The following conditions must be satisfied:

• There should be no cycles along roads after orientation.
• The city s should be the only such city that all its roads are oriented out (i.e. there are no ingoing roads to the city s and the city s is the only such city).
• The city t should be the only such city that all its roads are oriented in (i.e. there are no outgoing roads from the city t and the city t is the only such city).

Help the minister solve his problem. Write a program to find any such orientation of all roads or report that no solution exists.

Berland 由 $n$ 座城市和 $m$ 条双向道路组成，每条道路连接一对城市。不存在连接某座城市到其自身的道路，且任意两座城市之间至多只有一条道路。沿着道路可以从任意一座城市到达其他任意一座城市。

目前，总统先生位于城市 $s$，而他的目的地是城市 $t$。他计划沿道路从 $s$ 走到 $t$（其中 $s \neq t$）。

因此，愚人与道路部正面临艰难时期。该部部长担心总统先生可能遭遇交通拥堵或迷路，甚至谁也不知道还会发生什么！

为确保一切按计划进行，部长决定临时将所有道路改为单向通行。即：每条道路将被定向为两个可能方向中的一个。需满足以下条件：

• 定向后，道路上不能存在环；
• 城市 $s$ 必须是唯一一座所有关联道路均向外指向的城市（即：没有道路通向城市 $s$，且 $s$ 是唯一满足此性质的城市）；
• 城市 $t$ 必须是唯一一座所有关联道路均向内指向的城市（即：没有道路从城市 $t$ 出发，且 $t$ 是唯一满足此性质的城市）。

请帮助部长解决该问题：编写一个程序，找出任意一种满足上述要求的道路定向方案；若不存在这样的方案，则报告无解。

Each test in this problem contains one or more test cases to solve. The first line of the input contains positive number T — the number of cases to solve.

Each case starts with a line containing four integers n, m, s and t (2 ≤ n ≤ 4·105, 1 ≤ m ≤ 106, 1 ≤ s, t ≤ n, s ≠ t) — the number of cities, the number of roads and indices of departure and destination cities. The cities are numbered from 1 to n.

The following m lines contain roads, one road per line. Each road is given as two integer numbers x__j, y__j (1 ≤ x__j, y__j ≤ n, x__j ≠ y__j), which means that the j-th road connects cities x__j and y__j. There is at most one road between any pair of cities. It is possible to reach any city from any other moving along roads.

The sum of values n over all cases in a test doesn't exceed 4·105. The sum of values m over all cases in a test doesn't exceed 106.

本题的每个测试包含一个或多个待解决的测试用例。输入的第一行包含一个正整数 $T$ —— 待解决的测试用例数量。

每个测试用例以一行开始，该行包含四个整数 $n$、$m$、$s$ 和 $t$（$2 \leq n \leq 4\cdot10^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\cdot10^5$；在单个测试的所有用例中，$m$ 的总和不超过 $10^6$。

For each case print "Yes" if the answer exists. In the following m lines print roads in the required directions. You can print roads in arbitrary order. If there are multiple answers, print any of them.

Print the only line "No" if there is no answer for a case.

对于每组测试数据，若存在答案，则输出“Yes”。接下来的 m 行中，按要求的方向输出道路；道路的输出顺序可以任意。若存在多个可行答案，输出任意一个即可。

若该组测试数据无解，则仅输出一行“No”。