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;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vii;
typedef vector<pll> vll;
#define fi first
#define se second
const ll INFLL=LLONG_MAX;
const int INF=INT_MAX;
#define eb emplace_back
#define emp emplace
#define mp(a,b) make_pair(a,b)
template<class T> using min_heap=priority_queue<T,vector<T>,greater<T> >;
template<class T>
void sort(vector<T>& v){
	sort(v.begin(),v.end());
}
template <class T, class U>
void sort(vector<T>& v,U func){
	sort(v.begin(),v.end(),func);
}
template <class T>
int lb_index(vector<T>& v,T k){
	return lower_bound(v.begin(),v.end(),k)-v.begin();
}
template <class T>
int ub_index(vector<T>& v,T k){
	return upper_bound(v.begin(),v.end(),k)-v.begin();
}
int n,m;
vector<int>v[100000];
vector<int>st(100000,-1),et(100000,-1);
vector<int>low(100000);
vector<pair<int,int> >bridge;
int tim;
void dfs(int u,int p){
	st[u]=tim++;
	low[u]=st[u];
	for(auto i:v[u]){
		if(p==i)continue;
		if(st[i]==-1){
			dfs(i,u);
			low[u]=min(low[u],low[i]);
			if(st[u]<low[i]){
				bridge.emplace_back(u,i);
			}
		}
		else if(et[i]==-1){
			low[u]=min(low[u],st[i]);
		}
	}
	et[u]=tim;
}
int main(){
	cin>>n>>m;
	while(m--){
		int l,r;
		cin>>l>>r;
		v[l].emplace_back(r);
		v[r].emplace_back(l);
	}
	for(int i=0;i<n;i++){
		if(st[i]==-1)dfs(i,-1);
	}
	map<pii,bool>p;
	for(int i=0;i<bridge.size();i++){
		bridge[i]={min(bridge[i].fi,bridge[i].se),max(bridge[i].fi,bridge[i].se)};
	}
	sort(bridge);
	for(auto i:bridge){
		if(!p[i])cout<<min(i.fi,i.se)<<" "<<max(i.fi,i.se)<<"\n";
		p[i]=1;
	}
}