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<map>
#include<algorithm>
using namespace std;
const int max_n = 1000001, inf = 9999999;
pair<int, int>ans[1000000];
vector<int>adj[max_n];
int dp[max_n], depath[max_n], from[max_n], to[max_n];
bool vis[max_n];
int rt;
void dfs(int v, int de, int p){
	depath[v] = de;
	vis[v] = 1;
	for (int e : adj[v]){
		int a = from[e] ^ to[e] ^ v;
		if (e == p)
			continue;
		if (vis[a])
			dp[v] = min(dp[v], depath[a]);
		else{
			dfs(a, de + 1, e);
			dp[v] = min(dp[a], dp[v]);
		}
	}
	if (dp[v] >= de  &&p != -1)
		ans[rt] = { min(from[p], to[p]), max(from[p], to[p]) },rt++;
}
int main(){
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < max_n; i++)
		dp[i] = inf;
	for (int i = 1; i <= m; i++){
		cin >> from[i]>> to[i];
		from[i];
		to[i];
		adj[from[i]].push_back(i);
		adj[to[i]].push_back(i);
	}
	dfs(0, 0, -1);
	sort(ans, ans + rt);
	for (int i = 0; i < rt; i++)
		cout << ans[i].first << ' ' << ans[i].second << endl;
	int z;
	cin >> z;
}