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<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>

using namespace std;

int dfs(vector<vector<pair<int,int>>> &graph, vector<pair<int,int>> &res, int v, int &count, int from, vector<int> &low, vector<int> &pre){
	pre[v] = count++;
	low[v] = pre[v];
	
	for(pair<int,int> next : graph[v]){
		if(pre[next.first] == -1){
			
			low[v] = min(low[v], dfs(graph, res, next.first, count, v, low, pre));
			if(low[next.first] == pre[next.first]){
				if(v < next.first) res.push_back(make_pair(v, next.first));
				else res.push_back(make_pair(next.first, v));
			}
		} else {
			if(from == next.first){
				continue;
			}
			low[v] = min(low[v], pre[next.first]);
		}
	}
	
	return low[v];
}

vector<pair<int,int>> bridges(vector<vector<pair<int,int>>> & graph, int V){
	vector<pair<int,int>> res;
	
	if(V > 0){
		vector<int> low(V, -1);
		vector<int> pre(V, -1);
		int count = 0;
		dfs(graph, res, 0, count, -1, low, pre);
	}
	
	return res;
}


signed main(){
	
	int V, E;
	vector<vector<pair<int,int>>> G;
	vector<pair<int,int>> b;
	set<int> s;
	
	cin>>V>>E;
	
	G.resize(V);
	
	for(int i = 0; i < E; i++){
		int s, t;
		
		cin>>s>>t;
		
		G[s].push_back({t, 1});
		G[t].push_back({s, 1});
	}
	
	b = bridges(G, V);
	
	sort(b.begin(), b.end());
	
	for(int i = 0; i < b.size(); i++){
		cout<<b[i].first<<" "<<b[i].second<<endl;
	}
	
	return 0;
}