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:
//be naame khodaa
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
#define F first
#define S second

inline int in(){int x, y; y = scanf("%d", &x); return x; }

const int N = 200002, E = 200002;

vector <int> g[N], cvs;
vector <pair<int, int>> ces;
int up[N], h[N], from[E], to[E];
bool mark[N];

int cecvme(int v, int pare = -1) // With multiple edge
{
	up[v] = h[v];
	mark[v] = true;
	int children = 0;
	for(int e : g[v])
		if(e != pare)
		{
			int u = to[e] ^ from[e] ^ v;
			if(mark[u])
				up[v] = min(up[v], h[u]);
			else
			{
				h[u] = h[v] + 1;
				up[v] = min(up[v], cecvme(u, e));
				if(up[u] >= h[v] && pare != -1)
					cvs.push_back(v);
				children++;
			}
		}
	if(pare != -1 && up[v] == h[v])
		ces.push_back({from[pare], v}); // pare
	if(pare == -1 && children > 1)
		cvs.push_back(v);
	return up[v];
}
 
int cecv(int v, int par) // Without multiple edge
{
	up[v] = h[v];
	mark[v] = true;
	int children = 0;
	for(int u : g[v])
	{
		if(mark[u] && u != par)
			up[v] = min(up[v], h[u]);
		if(!mark[u])
		{
			h[u] = h[v] + 1;
			up[v] = min(up[v], cecv(u, v));
			if(up[u] >= h[v] && h[v] > 0)
				cvs.push_back(v);
			children++;
		}
	}
	if(h[v] > 0 && up[v] == h[v])
		ces.push_back({par, v});
	if(h[v] == 0 && children > 1)
		cvs.push_back(v);
	return up[v];
}

int main()
{
	h[0] = 0;
	int n = in(), m = in();
	for(int i = 0; i < m; i++)
	{
		int u = in(), v = in();
		g[u].push_back(v);
		g[v].push_back(u);
		from[i] = u;
		to[i] = v;
	}
	cecv(0, -1);
	for(auto &e : ces)
		if(e.first > e.second)
			swap(e.first, e.second);
	sort(ces.begin(), ces.end());
	for(auto e : ces)
		cout << e.first << " " << e.second << endl;
}