English · Original
Chinese · Translation
Formal · Original
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.
## Input
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.
## Output
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.
[samples]
Berland 由 #cf_span[n] 座城市和 #cf_span[m] 条双向道路组成，每条道路连接一对城市。没有道路连接城市到自身，且任意两个城市之间至多有一条道路。从任意一座城市出发，都可以通过道路到达其他任意城市。
目前总统位于城市 #cf_span[s]，他的目的地是城市 #cf_span[t]。他计划沿着道路从 #cf_span[s] 移动到 #cf_span[t]（#cf_span[s ≠ t]）。
因此，愚人与道路部正面临困难时期。部长担心总统可能遭遇交通堵塞或迷路。谁知道还会发生什么！
为确保一切按计划进行，部长决定暂时将所有道路改为单向。每条道路将被赋予两个可能方向中的一个。必须满足以下条件：
帮助部长解决这个问题。编写一个程序，找到任意一种满足条件的道路定向方案，或报告无解。
本题每个测试点包含一个或多个测试用例。输入的第一行包含正整数 #cf_span[T] —— 需要解决的用例数量。
每个用例以一行四个整数 #cf_span[n], #cf_span[m], #cf_span[s] 和 #cf_span[t] 开始（#cf_span[2 ≤ n ≤ 4·105], #cf_span[1 ≤ m ≤ 106], #cf_span[1 ≤ s, t ≤ n], #cf_span[s ≠ t]），分别表示城市数量、道路数量以及起点和终点城市的编号。城市编号从 #cf_span[1] 到 #cf_span[n]。
接下来的 #cf_span[m] 行每行描述一条道路，格式为两个整数 #cf_span[xj], #cf_span[yj]（#cf_span[1 ≤ xj, yj ≤ n], #cf_span[xj ≠ yj]），表示第 #cf_span[j] 条道路连接城市 #cf_span[xj] 和 #cf_span[yj]。任意两个城市之间至多有一条道路，且任意城市均可通过道路到达其他任意城市。
所有测试用例中 #cf_span[n] 的总和不超过 #cf_span[4·105]，所有测试用例中 #cf_span[m] 的总和不超过 #cf_span[106]。
对于每个用例，若存在解，输出 "_Yes_"；接着在接下来的 #cf_span[m] 行中输出每条道路的定向结果（可任意顺序输出）。若有多个解，输出任意一个即可。
若无解，仅输出一行 "_No_"。
## Input
Each test in this problem contains one or more test cases to solve. The first line of the input contains positive number #cf_span[T] — the number of cases to solve.Each case starts with a line containing four integers #cf_span[n], #cf_span[m], #cf_span[s] and #cf_span[t] (#cf_span[2 ≤ n ≤ 4·105], #cf_span[1 ≤ m ≤ 106], #cf_span[1 ≤ s, t ≤ n], #cf_span[s ≠ t]) — the number of cities, the number of roads and indices of departure and destination cities. The cities are numbered from #cf_span[1] to #cf_span[n].The following #cf_span[m] lines contain roads, one road per line. Each road is given as two integer numbers #cf_span[xj], #cf_span[yj] (#cf_span[1 ≤ xj, yj ≤ n], #cf_span[xj ≠ yj]), which means that the #cf_span[j]-th road connects cities #cf_span[xj] and #cf_span[yj]. 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 #cf_span[n] over all cases in a test doesn't exceed #cf_span[4·105]. The sum of values #cf_span[m] over all cases in a test doesn't exceed #cf_span[106].
## Output
For each case print "_Yes_" if the answer exists. In the following #cf_span[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.
[samples]
**Definitions**
Let $ G = (V, E) $ be an undirected connected graph with $ |V| = n $, $ |E| = m $, and distinct vertices $ s, t \in V $, $ s \ne t $.
**Constraints**
1. $ 2 \le n \le 4 \cdot 10^5 $, $ 1 \le m \le 10^6 $
2. $ G $ is connected and simple (no self-loops, no multiple edges).
3. The total sum of $ n $ across test cases $ \le 4 \cdot 10^5 $.
4. The total sum of $ m $ across test cases $ \le 10^6 $.
**Objective**
Find an orientation of all edges in $ E $ such that there exists a directed path from $ s $ to $ t $. If such an orientation exists, output "Yes" followed by one directed edge per original undirected edge; otherwise, output "No".
API Response (JSON)
{
"problem": {
"name": "K. Roads Orientation Problem",
"description": {
"content": "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 i",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 5000,
"memory_limit": 524288
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF730K"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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 i...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Berland 由 #cf_span[n] 座城市和 #cf_span[m] 条双向道路组成，每条道路连接一对城市。没有道路连接城市到自身，且任意两个城市之间至多有一条道路。从任意一座城市出发，都可以通过道路到达其他任意城市。\n\n目前总统位于城市 #cf_span[s]，他的目的地是城市 #cf_span[t]。他计划沿着道路从 #cf_span[s] 移动到 #cf_span[t]（#cf_sp...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ G = (V, E) $ be an undirected connected graph with $ |V| = n $, $ |E| = m $, and distinct vertices $ s, t \\in V $, $ s \\ne t $. \n\n**Constraints** \n1. $ 2 \\le n \\le 4 \\cdot 10...",
"is_translate": false,
"language": "Formal"
}
]
}