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;

template<class T>
struct Edge{
	int from,to;
	T cost;
	Edge(int to,T cost) : to(to),cost(cost){}
	Edge(int from,int to,T cost) : from(from),to(to),cost(cost){}
	operator int() const noexcept { return to; }
};

template<class T>
using WeightedGraph = vector<vector<Edge<T>>>;
using Graph = vector<vector<int>>;
template<class T>
using Matrix = vector<vector<T>>;

template<class T>
struct TwoEdgeConnectedComponents{
	T G;
	vector<int> cmp,depth,s;
	vector<vector<int>> tecc;
	stack<int> vs;
	using pii = pair<int,int>;
	vector<pii> bridge;

	TwoEdgeConnectedComponents(const T &G) : G(G),cmp(G.size()),depth(G.size(),-1),s(G.size()){}

	void dfs(int v,int par,int d){
		depth[v] = d;
		vs.push(v);
		for(const auto &e : G[v]){
			int to = (int)e;
			if(depth[to] == -1){
				dfs(to,v,d + 1);
				s[v] += s[to];
			}else if(to != par && depth[v] > depth[to]) s[to]--,s[v]++;
		}
		if(!s[v]){
			if(par != -1) bridge.push_back(minmax(v,par));
			tecc.emplace_back();
			while(1){
				int u = vs.top(); vs.pop();
				tecc.back().push_back(u);
				cmp[u] = tecc.size() - 1;
				if(u == v) break;
			}
		}
	}

	void build(){
		for(int i = 0;i < G.size();i++) if(depth[i] == -1) dfs(i,-1,0);
	}
};

signed main(){
	int n,m;
	cin >> n >> m;
	Graph G(n);
	for(int i = 0;i < m;i++){
		int a,b;
		cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	TwoEdgeConnectedComponents<Graph> tecc(G);
	tecc.build();
	sort(tecc.bridge.begin(),tecc.bridge.end());
	for(const auto &e : tecc.bridge) cout << e.first << " " << e.second << endl;
}