Problem: Find bridges of an undirected graph G(V, E).

A bridge (also known as a cut-edge) is an edge whose deletion increase the number of connected components.

Constraints

* 1 ≤ |V| ≤ 100,000
* 0 ≤ |E| ≤ 100,000
* The graph is connected
* There are no parallel edges
* There are no self-loops

Input


|V| |E|
s0 t0
s1 t1
:
s|E|-1 t|E|-1


, where |V| is the number of nodes and |E| is the number of edges in the graph. The graph nodes are named with the numbers 0, 1,..., |V|-1 respectively.

si and ti represent source and target nodes of i-th edge (undirected).

Output

A list of bridges of the graph ordered by name. For each bridge, names of its end-ponints, source and target (source < target), should be printed separated by a space. The sources should be printed ascending order, then the target should also be printed ascending order for the same source.

Examples

Input

4 4
0 1
0 2
1 2
2 3


Output

2 3


Input

5 4
0 1
1 2
2 3
3 4


Output

0 1
1 2
2 3
3 4

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

#define N 100005

int n, m;

class edge
{
	private:
		int fr, to;
		
	public:	
		edge(void) {};
		edge(int u, int v)
		{
			fr = min(u, v);
			to = max(u, v);
		}
		
		int u(void)
		{
			return fr;
		}
		
		int v(void)
		{
			return to;
		}
		
		int another(int one)
		{
			return one == fr ? to : fr;
		}
		
		friend bool operator < (const edge &a, const edge &b)
		{
			return a.fr != b.fr ? a.fr < b.fr : a.to < b.to;
		}
}E[N];

vector<int> to[N];

vector<edge> answer;

int dfn[N], low[N], tim;

void tarjan(int u, int f)
{
	dfn[u] = low[u] = ++tim;
	
	for (auto i : to[u])
		if (i != f)
		{
			edge e = E[i];
			int v = e.another(u);
			
			if (!dfn[v])
			{
				tarjan(v, i);
				low[u] = min(low[u], low[v]);
			}
			else
				low[u] = min(low[u], dfn[v]);
		}
		
	if (u && dfn[u] <= low[u])
		answer.push_back(E[f]);
}

signed main(void) 
{
	cin >> n >> m;
	
	for (int u, v; m--; )
	{
		cin >> u >> v;
		E[m] = edge(u, v);
		to[u].push_back(m);
		to[v].push_back(m);
	}
	
	tarjan(0, -1);
	
	sort(begin(answer), end(answer));
	
	for (auto e : answer)
		cout << e.u() << " " << e.v() << endl;
}