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<algorithm>
using namespace std;
class Bridge {
private:
	int size_, cnt0; vector<vector<int>>x; vector<int> ord, low, used; vector<pair<int, int>>brd;
public:
	Bridge() : size_(0), x(vector<vector<int>>()) {};
	Bridge(int size__) : size_(size__) {
		x.resize(size__);
		ord.resize(size__);
		low.resize(size__);
		used.resize(size__);
	}
	void unite(int a1, int a2) {
		x[a1].push_back(a2);
		x[a2].push_back(a1);
	}
	void dfs(int p, int k) {
		low[p] = cnt0; used[p] = 1;
		ord[p] = cnt0; cnt0++;
		for (int i = 0; i < x[p].size(); i++) {
			int to = x[p][i];
			if (used[to] == 0) {
				dfs(to, p);
				low[p] = min(low[p], low[to]);
				if (ord[p] < low[to]) {
					int aa1 = p, aa2 = to; if (aa1 > aa2)swap(aa1, aa2);
					brd.push_back(make_pair(aa1, aa2));
				}
			}
			else if (to != k) {
				low[p] = min(low[p], ord[to]);
			}
		}
	}
	vector<pair<int, int>> bridge(int size__, int st) {
		brd.clear(); cnt0 = 0;
		for (int i = 0; i < size__; i++) { ord[i] = 0; low[i] = 0; used[i] = 0; }
		dfs(st, -1);
		return brd;
	}
	int size() { return size_; }
};
int main() {
	int n, m, a, b; cin >> n >> m;
	Bridge B(n + 1);
	for (int i = 0; i < m; i++) {
		cin >> a >> b; B.unite(a, b);
	}
	vector<pair<int, int>>W = B.bridge(n + 1, 1);
	sort(W.begin(), W.end());
	for (int i = 0; i < W.size(); i++)cout << W[i].first << ' ' << W[i].second << endl;
	return 0;
}