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:
//??£?????°????????¨????????????
//????????????????????????????????? (????????????????????¨?????°?????????DFS??¨??????????????????)
//???DFS??¨?????????u(???root)???????????????lowlink[u] > prenum[u??????] ??? u?????? --> u?????? (??¨??????)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Edge {
	int u, v;
	Edge(int u, int v) { this->u = u; this->v = v; }
	Edge() { }
	bool operator<(const Edge &r) const { return (u != r.u) ? u < r.u : v < r.v; }
};

int n, m;
vector<int> et[100000];

int timer;
bool visited[100000];
int prenum[100000];
int lowest[100000];
int parent[100000];

void dfs(int u, int prev) {
	prenum[u] = timer;
	lowest[u] = timer;
	parent[u] = prev;
	visited[u] = true;
	timer++;
	
	for (int i = 0; i < et[u].size(); i++) {
		int v = et[u][i];
		
		if (!visited[v]) {
			dfs(v, u);
			lowest[u] = min(lowest[u], lowest[v]);
		}
		else if (parent[u] != v) {
			//u --> v????????????
			lowest[u] = min(lowest[u], prenum[v]);
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int src, dst;
		cin >> src >> dst;
		et[src].push_back(dst);
		et[dst].push_back(src);
	}
	
	//????????????
	timer = 0;
	for (int i = 0; i < n; i++) visited[i] = false;
	dfs(0, -1);
	
	static vector<Edge> ans;
	
	for (int i = 1; i < n; i++) {
		if (prenum[parent[i]] < lowest[i]) {
			ans.push_back(Edge(min(parent[i], i), max(parent[i], i)));
		}
	}
	
	sort(ans.begin(), ans.end());
	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i].u << " " << ans[i].v << endl;
	}
	
	return 0;
}