Oprava orientace hran v grafu

Zadání

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 ≤ 10⁶.

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říklady

Příklad 1

Vstup

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

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

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