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 <bits/stdc++.h>
using namespace std;


struct low_link {
public :
	vector<int> articulation;
	vector<pair<int, int>> bridge;
private :
	struct edge {
		int to, idx;
		edge (int to, int idx) : to(to), idx(idx) { }
	};
	int n, edge_index = 0;
	vector<vector<edge>> g;
	vector<int> order, low;
	vector<bool> seen;

	int dfs (int v, int p, int ord) {
		seen[v] = true;
		order[v] = ord++;
		low[v] = order[v];
		int child = 0;
		bool isart = false;
		for (const edge &e : g[v]) if (p != e.idx) {
			if (seen[e.to]) {
				low[v] = min(low[v], order[e.to]);
			} else {
				child++;
				ord = dfs(e.to, e.idx, ord);
				low[v] = min(low[v], low[e.to]);
				if (p != -1) isart |= (order[v] <= low[e.to]);
				if (order[v] < low[e.to]) {
					bridge.push_back(minmax(v, e.to));
				}
			}
		}
		isart |= (p == -1 and child >= 2);
		if (isart) articulation.push_back(v);
		return ord;
	}

public :
	low_link (int n) : n(n), g(n), order(n), low(n), seen(n) { }

	void add_edge (int v, int u) {
		g[v].emplace_back(u, edge_index);
		g[u].emplace_back(v, edge_index);
		edge_index++;
	}

	void build (int r = 0) {
		bridge.clear(); articulation.clear();
		fill(seen.begin(), seen.end(), false);
		for (int s = 0; s < g.size(); s++) {
			if (not seen[s]) dfs(s, -1, 0);
		}
	}

};


int main() {
	int n, m;
	cin >> n >> m;
	low_link g(n);
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		g.add_edge(a, b);
	}
	
	g.build();
	sort(g.bridge.begin(), g.bridge.end());
	for (pair<int, int> e : g.bridge) {
		cout << e.first << ' ' << e.second << '\n';
	}
	
	return 0;
}