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 <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>
#include <deque>
#include <complex>

using namespace std;

#define mod 1000000007

vector<vector<int> > graph(100001);
vector<int> pre(100001, -1);
vector<int> low(100001, -1);

int dfs(int now, int before, int cnt)
{
	pre[now] = cnt;
	low[now] = cnt;
	for(int i = 0; i < graph[now].size(); i++){
		int next = graph[now][i];
		if(next == before) continue;
		if(pre[next] == -1){
			cnt = dfs(next, now, cnt + 1);
		}
		low[now] = min(low[now], low[next]);
	}
	// cout << now << " " << pre[now] << " " << low[now] << endl;
	return cnt;
}

int main()
{
	int v, e;
	cin >> v >> e;
	for(int i = 0; i < e; i++){
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	dfs(0, -1, 0);
	vector<pair<int, int> > ans;
	for(int i = 0; i < v; i++){
		for(int j = 0; j < graph[i].size(); j++){
			int next = graph[i][j];
			if(pre[i] < pre[next] && pre[next] == low[next]) ans.push_back(make_pair(min(i, next), max(i, next)));
		}
	}
	sort(ans.begin(), ans.end());
	for(int i = 0; i < ans.size(); i++){
		cout << ans[i].first << " " << ans[i].second << endl;
	}
}