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<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#include<sstream>
#include<iomanip>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef pair<int,pii> pip;
typedef vector<pip>vip;
const double PI=acos(-1);
const double EPS=1e-8;
const int inf=1e8;
class BRI{
	public:
	int N;
	vi used;
	vvi G;
	vp bridge;
	void add_edge(int s,int t){
		G[s].pb(t);
		G[t].pb(s);
	}
	BRI(int size){
		N=size;
		G=vvi(N);
	}
	int dfs(int i,int prev,int &n){
		if(used[i])return used[i];
		int m=n;
		used[i]=n++;
		rep(j,G[i].size()){
			if(prev==G[i][j])continue;
			if(used[i]<used[G[i][j]])continue;
			int res=dfs(G[i][j],i,n);
			m=min(m,res);
			if(used[i]<res)bridge.pb(pii(min(i,G[i][j]),max(i,G[i][j])));
		}
		return m;
	}
	void bri(){
		used=vi(N);
		bridge=vp(0);
		int n=1;
		rep(i,N)if(!used[i])dfs(i,-1,n);
		sort(all(bridge));
		rep(i,bridge.size())cout<<bridge[i].first<<" "<<bridge[i].second<<endl;
	}
};
int main(){
	int n,m;
	cin>>n>>m;
	BRI bri(n);
	while(m--){
		int a,b;
		cin>>a>>b;
		bri.add_edge(a,b);
	}
	bri.bri();
}