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<bits/stdc++.h>
using namespace std;
const int MAX=1e6+9;
int par[MAX], low[MAX], vis[MAX], dis[MAX];
vector<int>adj[MAX];
int cnt=0,n ,m;
vector<pair<int, int> >ans;
void dfs(int vertex ,int p ){
	low[vertex]=dis[vertex]=cnt++;
	vis[vertex]=1;
	par[vertex]=p;
	for(int i=0;i<adj[vertex].size();i++){
		if(!vis[adj[vertex][i]]){
			par[adj[vertex][i]]=vertex;
			dfs(adj[vertex][i], vertex);
			low[vertex]=min(low[vertex], low[adj[vertex][i]]);
		}
		else if(p!=adj[vertex][i])
			low[vertex]=min(low[vertex] , dis[adj[vertex][i]]);
	}

}
void bridges(){
	par[0]=-1;
	dfs(0, -1);
	for(int i=0;i<n;i++){
		if(dis[par[i]]<low[i]){
			ans.push_back(make_pair(min(i ,par[i]), max(i, par[i])));
		}
	}
	sort(ans.begin(), ans.end());
	for(int i=0;i<ans.size();i++){
		cout<<ans[i].first<<" "<<ans[i].second<<endl;
	}
}
int main(){
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int x,y;
		cin>>x>>y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	bridges();

}