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 JAVA):

Solution:
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
	
	static int[] parent, prenum, lowest;
	static int timer=0;
	static boolean[] visited;
	static int V;
	static boolean[][] G;
	static PriorityQueue<State> pq=new PriorityQueue<>();
	
	static class State implements Comparable<State>{
		int s, t;
		State(int s, int t){
			this.s=s;
			this.t=t;
		}
		public int compareTo(State p) {
			if(p.s==this.s) {
				return this.t-p.t;
			}
			return this.s-p.s;
		}
	}
	
	
	static void dfs(int current, int prev) {
		prenum[current]=lowest[current]=timer;
		timer++;
		visited[current]=true;
		int next=0;
		for(int i=0; i<V; i++) {
			if(G[current][i]) {
				next=i;
				if(!visited[next]) {
					parent[next]=current;
					dfs(next, current);
					lowest[current]=Math.min(lowest[current], lowest[next]);
				}
				else if(next != prev) {//currentからnextがbackedgeの時
					lowest[current]=Math.min(lowest[current], prenum[next]);
				}
			}
		}

	}

	static void art_point() {
		for(int i=0; i<V; i++) {
			visited[i]=false;
		}
		timer=1;
		dfs(0, -1);
//		for(int i=0; i<V; i++) {
//			System.out.println("prenum["+i+"]="+prenum[i]+" lowest["+i+"]="+lowest[i]);
//		}
		
		for(int i=1; i<V; i++) {
			int p=parent[i];
			if(prenum[p]<lowest[i]) {
				pq.add(new State(Math.min(p, i), Math.max(p, i)));
				//System.out.println(Math.min(i, p)+" "+Math.max(i, p));
			}
		}
		
		while(! pq.isEmpty()) {
			State p=pq.remove();
			System.out.println(p.s+" "+p.t);
		}
		
	}
	
	public static void main(String[] args) {
		try(Scanner sc = new Scanner(System.in)){
			V=sc.nextInt();
			int E=sc.nextInt();
			parent=new int[V];
			prenum=new int[V];
			lowest=new int[V];
			visited=new boolean[V];
			G=new boolean[V][V];
			for(int i=0; i<E; i++) {
				int s=sc.nextInt();
				int t=sc.nextInt();
				G[s][t]=G[t][s]=true;
			}
			art_point();
			
		}
	}
}