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 <iostream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;
typedef pair<int, int> P;

int V, E;
vector<int> G[100005];
vector<P> bridge;
int pre[100005], low[100005];

int id = 1;
int bridge_dfs(int v, int prev)
{
	pre[v] = id++;
	int ret = pre[v];
	for(int i = 0; i < G[v].size(); i++){
		if(G[v][i] == prev) continue;
		if(pre[G[v][i]]) ret = min(ret, pre[G[v][i]]);
		else ret = min(ret, bridge_dfs(G[v][i], v));
	}
	return low[v] = ret;
}
void findBridge()
{
	bridge_dfs(1, -1);
	for(int i = 1; i <= V; i++){
		for(int j = 0; j < G[i].size(); j++){
			if(pre[i] < pre[G[i][j]] && low[G[i][j]] > pre[i]) bridge.push_back(make_pair(i, G[i][j]));
		}
	}
}

int main(void)
{
	cin >> V >> E;
	int u, v;
	for(int i = 1; i <= E; i++){
		cin >> u >> v;
		u++, v++;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	
	findBridge();
	
	for(int i = 0; i < bridge.size(); i++){
		if(bridge[i].first > bridge[i].second) swap(bridge[i].first, bridge[i].second);
	}
	sort(bridge.begin(), bridge.end());
	
	for(int i = 0; i < bridge.size(); i++){
		cout << bridge[i].first-1 << " " << bridge[i].second-1 << endl;
	}
	
	return 0;
}