Problem B
Vegaframkvæmdir

Þessa dagana eru miklar framkvæmdir í kringum Háskóla Íslands. Til þess að gera allar framkvæmdir sem nauðsynlegar eru þarf að loka þónokkuð mörgum akreinum á vegum í kringum Háskólann. Nóg til þess að allir vegir munu tímabundið verða að einstefnum. Þetta er auðvitað óheppilegt og ekki hjá því komist að ferðalengdir lengist hjá sumum. Háskólinn vill hins vegar sjá til þess að allir komist leiða sinna. Er hægt að velja áttun á einstefnum þannig að hægt sé að komast frá hvaða vegamótum sem er að hvaða öðrum vegamótum sem er?

Inntak

Inntakið byrjar á einni línu með tveimur heiltölum $1\le n,m\le {10}^5$ þar sem $n$ er fjöldi vegamóta og $m$ er fjöldi vega. Vegamótin eru númeruð frá $1$ og upp í $n$. Næst fylgja $m$ línur, hver með tveimur heiltölum $1\le a,b\le n$. Þetta merkir að til staðar sé tvístefnuvegur milli $a$ og $b$. Engin vegamót eru tengd sjálfum sér og hvert par vegamóta kemur að mestu fram einu sinni í inntakinu.

Úttak

Ef ekki er hægt að velja stefnur þannig að hægt sé að komast frá hvaða vegamótum sem er í hvaða önnur vegamót sem er skal prenta ‘Ekki haegt’. Annars skal prenta út $m$ línur. Hver lína skal innihalda tvær heiltölur $1\le a,b\le n$, sem segja að vegur sé frá vegamótum $a$ til vegamóta $b$. Upprunalega vegakerfið þarf að innihalda vega á milli vegamótanna og hvert par af vegamótum í upprunarlega vegakerfinu þarf að koma fyrir nákvæmlega einu sinni í úttakinu.

5 6
1 2
3 2
3 1
4 5
3 5
3 4

1 2
2 3
3 1
3 5
5 4
4 3

6 7
1 2
2 3
3 1
4 5
5 6
6 4
4 3

Ekki haegt