Given an undirected graph with $n$ vertices and $m$ edges, find all the bridges in the graph.

Input

The first line contains two positive integers $n$ and $m$.

The next $m$ lines each contain two positive integers $x$ and $y$, representing an edge between $x$ and $y$.

Output

Output several lines, each containing one edge, representing all the bridges. Output them in the order they appear in the input, and do not swap the order of the two endpoints.

The graph may contain multiple edges and self-loops.

Examples

Input 1

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

Output 1

5 6

Input 2

10 13
1 2
2 3
3 4
4 5
1 5
2 5
1 6
6 7
6 8
6 9
8 9
9 10
9 10

Output 2

1 6
6 7

Subtasks

For all data, $1 \leq n \leq 10^5$, $1 \leq x, y \leq n$, $1 \leq m \leq 5 \times 10^5$.