Scroll down to see the problem assignment in English

Oprava orientace hran v grafu

V daném orientovaném grafu jsou určeny dva různé uzly: Výchozí uzel A a koncový uzel B. Je známo, že z A do B nevede žádná orientovaná cesta. Je také známo, že v grafu stačí obrátit orientaci pouze jediné hrany a poté již orientovaná cesta z A do B existovat bude. Každou takovou hranu nazveme hranou jednoduše separující dvojici uzlů (A, B). Může se stát, že v grafu existuje více hran s touto vlastností.

     


Obrázek 1. Grafy a), b), c) odpovídají datům v příkladech 1, 2 a 3 níže. Všechny hrany jednoduše separující dvojici uzlů (A, B) jsou v každém grafu červeně zvýrazněny.

Úloha

Je dán orientovaný graf, výchozí uzel A a koncový uzel B. Najděte a vypište všechny hrany jednoduše separující dvojici uzlů (A, B).

Vstup

První řádek vstupu obsahuje čtyři celá čísla N, E, A, B oddělená mezerami. Hodnota N udává počet uzlů v grafu, hodnota E udává počet hran v grafu a čísla A resp. B označují počáteční rep. koncový uzel cesty v grafu. Uzly grafu jsou číslovány od 0 do N−1. Dále následuje E řádků, každý popisuje jednu hranu grafu. Řádek obsahuje nejprve číslo počátečního uzlu hrany a za mezerou číslo koncového uzlu hrany. Hrany jsou na vstupu uvedeny v libovolném pořadí.
Platí N ≤ 50000, E ≤ 106.

Výstup

Na výstupu je seznam všech hran jednoduše separujících dvojici uzlů (A, B). Hrany jsou uspořádány v rostoucím pořadí svých původních počátečních uzlů, pokud se počáteční uzly shodují, je uvedena dříve hrana s nižším číslem koncového uzlu. Každá hrana na výstupu je zapsána na jednom řádku a má stejný formát jako hrany na vstupu. Je zaručeno, že výstupní seznam hran má nejvýše 10 položek.

Příklad 1

Vstup
6 8 2 3
2 0
1 0
1 3
3 5
5 4
4 2
0 4
5 1
Výstup
1 0
5 4
Data a řešení příkladu 1 jsou znázorněna na obrázku 1a).

Příklad 2

Vstup
8 13 0 7
0 1
1 2
2 3
3 4
4 5
6 0
6 5
6 7
7 0
0 5
1 5
1 4
2 4
Výstup
6 0
6 5
7 0
Data a řešení příkladu 2 jsou znázorněna na obrázku 1b).

Příklad 3

Vstup
9 10 5 3
1 0
1 2
0 3
3 6
1 4
4 7
5 2
5 8
6 7
8 7
Výstup
1 2
Data a řešení příkladu 3 jsou znázorněna na obrázku 1c).

Veřejná data

Veřejná data k úloze jsou k dispozici. Veřejná data jsou uložena také v odevzdávacím systému a při každém odevzdání/spuštění úlohy dostává řešitel kompletní výstup na stdout a stderr ze svého programu pro každý soubor veřejných dat.
Veřejná data




Simply separating edges

Two different nodes A and B are specified in a directed graph G. It is known that there exists no directed path from A to B in G. On the other hand, it is know that it is enough to reverse the direction of a single edge in G and after this reversal there would exist a directed path from A to B. We say that any such edge in G is an edge simply separating node pair (A, B). It is possible that there are more edges in G with this property.

     


Image 1. Graphs a), b), c) correspond to Examples 1, 2, 3, respectively. All edges in all graphs which are simply separating node pair (A, B) are highlighted in red.

The Task

You are given a directed graph and two nodes A and B. Find and print out all edges simply separating node pair (A, B).

Input

The first input line contains four positive integers N, E, A, B separated by spaces. N is the number of nodes in the graph, the nodes are labeled 0,1, ..., N−1. E is the number of edges in the graph, A and B are labels of two different nodes in the graph. Next, there are E lines, each line represents one edge. The line contains the labels of the source and the target node of the edge, the labels are separated by space. The edges are listed in no particular order.
It holds N ≤ 50000, E ≤ 106.

Output

The output contains the list of all edges simply separating node pair (A, B) in the given graph. The edges are sorted in increasing order of their source nodes. When the source nodes of two edges are equal then the edge with lower target node label is listed first. Each edge is listed on a separate line and it follows the format of the input edges. There are no more than 10 edges in the list.

Example 1

Input
6 8 2 3
2 0
1 0
1 3
3 5
5 4
4 2
0 4
5 1
Output
1 0
5 4
The data and the solution of Example 1 are depicted in Image 1a).

Example 2

Input
8 13 0 7
0 1
1 2
2 3
3 4
4 5
6 0
6 5
6 7
7 0
0 5
1 5
1 4
2 4
Output
6 0
6 5
7 0
The data and the solution of Example 2 are depicted in Image 1b).

Example 3

Input
9 10 5 3
1 0
1 2
0 3
3 6
1 4
4 7
5 2
5 8
6 7
8 7
Output
1 2
The data and the solution of Example 3 are depicted in Image 1c).

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set