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;
int v, e;
pair<int, int> a[200010];
int s[100001];
int g[100001];
int n[100001];
int p[100001];
int l[100001];
int u[100001]={};
int c, t;
int x, y;
int k;

void dfs(int f, int z)
{
	n[f]=t;
	l[f]=t;
	t++;
	u[f]=1;
	for(int i=s[f]; i<=g[f]; i++)
	{
		if(u[a[i].second]==0)
		{
			p[a[i].second]=f;
			dfs(a[i].second, f);
			l[f]=min(l[f], l[a[i].second]);
		}
		else if(a[i].second!=z)
		{
			l[f]=min(l[f], n[a[i].second]);
		}
	}
}

int main()
{
	cin >> v >> e;
	for(int i=0; i<e; i++)
	{
		cin >> x >> y;
		a[2*i]=make_pair(x, y);
		a[2*i+1]=make_pair(y, x);
	}
	sort(a, a+(2*e));
	s[0]=0;
	g[v-1]=2*e-1;
	c=0;
	for(int i=1; i<2*e; i++)
	{
		if(a[i].first>a[i-1].first)
		{
			g[c]=i-1;
			c++;
			s[c]=i;
		}
	}
	t=0;
	dfs(0, -1);
	k=0;
	for(int i=1; i<v; i++)
	{
		if(p[i]==0)
		{
			k++;
		}
	}
	if(k>1)
	{
		for(int i=s[0]; i<=g[0]; i++)
		{
			if(p[a[i].second]==0)
			{
				cout << 0 << " " << a[i].second << endl;
			}
		}
	}
	else if(s[0]==g[0])
	{
		cout << 0 << " " << a[g[0]].second << endl;
	}
	for(int i=s[1]; i<2*e; i++)
	{
		if(a[i].first<a[i].second)
		{
			if(p[a[i].first]==a[i].second)
			{
				if(n[a[i].second]<l[a[i].first])
				{
					cout << a[i].first << " " << a[i].second << endl;
				}
			}
			else if(p[a[i].second]==a[i].first)
			{
				if(n[a[i].first]<l[a[i].second])
				{
					cout << a[i].first << " " << a[i].second << endl;
				}
			}
		}
	}
	return 0;
}