Problem B
Vegaframkvæmdir

There has been a lot of road work around HÍ recently. A necessary part of these constructions is the closing of some lanes. It has gotten to the point that all roads will temporarily be made unidirectional. It is of course important to the university that everyone can still travel to their destination. Is it possible to choose a direction on all the roads such that you can get from each intersection to every other?

Input

The first line of the input consists of two integers $1 \leq n, m \leq 10^5$ where $n$ is the number of intersections and $m$ is the number of roads. The intersections are numbered from $1$ to $n$. Next follow $m$ lines, each with two integers $1 \leq u, v \leq n$. This indicates a road between intersections $a$ and $b$. It is guaranteed that no intersection is connected to itself and no two intersections are connected by more than one road.

Output

If it is not possible to choose directions such that you can get from each intersection to every other print ‘Ekki haegt’. Otherwise print $m$ lines. Each line should contain two integers $1 \leq a, b \leq m$, indicating a unidirectional road from intersection $a$ to intersection $b$. The original road system must include a road between the two intersections and each pair of intersection in the original road system must appear exactly once in the output.

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