Given an undirected graph with $n$ vertices and $m$ edges, find all bridges in the graph. A bridge is an edge whose removal increases the number of connected components of the graph.

Input

The first line contains two positive integers $n$ and $m$, representing the number of vertices and edges in the graph, respectively.

The next $m$ lines each contain two non-negative integers $u$ and $v$, representing an edge between $u$ and $v$. It is guaranteed that $1 \le u, v \le n$.

Output

Output all bridges found in the graph. Each bridge should be printed on a new line as two positive integers representing the two endpoints of the edge.

Subtasks

Each subtask is worth 10 points.

Examples

Input 1

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

Output 1

1 8
9 10