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 <fstream>
#include <typeinfo>
#include <vector>
#include <cmath>
#include <map>
#include <string>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <iomanip>
#include <cctype>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<bool> vb;
typedef vector<vp> vvp;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const double pi=acos(-1);
const double eps=1e-8;

class Graph{
	private:
	int GV,GE;
	vvi List;
	void bridgefunc(int x,vb& used,vi& disc,vi& low,vi& par){
		static int time=0;
		used[x]=1;
		disc[x]=low[x]=++time;
		for(int i=0;i<List[x].size();i++){
			int v=List[x][i];
			if(!used[v]){
				par[v]=x;
				bridgefunc(v,used,disc,low,par);
				low[x]=min(low[x],low[v]);
				if(low[v]>disc[x]){
					if(v<x) br.push_back(P(v,x));
					else br.push_back(P(x,v));
				}
			}
			else if(v!=par[x]) low[x]=min(low[x],disc[v]);
		}
	}
	public:
	vp br;
	Graph(int v,int e){
		GV=v;
		GE=e;
		List=vvi(v);
	}
	void add_edge(int x,int y){
		List[x].push_back(y);
		List[y].push_back(x);
	}
	void bridge(){
		vb used(GV);
		vi disc(GV),low(GV),par(GV,-1);
		for(int i=0;i<GV;i++){
			if(!used[i]) bridgefunc(i,used,disc,low,par);
		}
	}
};

int V,E;

int main(){
	cin>>V>>E;
	Graph gra(V,E);
	int s,t;
	for(int i=0;i<E;i++){
		cin>>s>>t;
		gra.add_edge(s,t);
	}
	gra.bridge();
	sort(gra.br.begin(),gra.br.end());
	for(int i=0;i<gra.br.size();i++){
		cout<<gra.br[i].first<<' '<<gra.br[i].second<<endl;
	}
}