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.io.IOException;
import java.io.InputStream;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        FastScanner sc = new FastScanner();
         
        int v = sc.nextInt();
        int e = sc.nextInt();
        
        SGraph g = new SGraph(v);
        
        for(int i=0;i<e;i++){
        	g.addEdge(sc.nextInt(), sc.nextInt());
        }
        
        ArrayList<SGraph.EdgePair> l = g.bridge();
        Collections.sort(l);
        for(SGraph.EdgePair p:l){
        	System.out.println(p.a + " " + p.b);
        }
        
    }
	
}

class SGraph {

	NodeList[] nlist; //隣接リスト
	
	public SGraph(int vnum){
		this.nlist = new NodeList[vnum];
		for(int i=0;i<vnum;i++){
			nlist[i] = new NodeList();
		}
	}
	
	//辺の追加（同じ辺を複数回追加すると多重辺になる）
	void addEdge(int n, int m){
		nlist[n].add(m);
		nlist[m].add(n);
	}
	
	//頂点数を返す
	int vnum(){
		return nlist.length;
	}
	
	//辺数を返す
	int edgeNum(){
		int sum = 0;
		for(NodeList l:nlist){
			sum += l.size();
		}
		return sum/2;
	}
	
	//隣接判定
	boolean isNext(int n, int m){
		return nlist[n].contains(m);
	}
	
	//隣接する全ての頂点を返す
	NodeList nextList(int n){
		return nlist[n];
	}
	
	//含まれる木の数を返す
	int treeNum(){
    	boolean[] isVisited = new boolean[vnum()];
    	int[] par = new int[vnum()];
    	int TreeNum = 0;
    	
    	boolean con = true;
    	
    	while(con){
    		int core = -1;
    		
    		for(int i=0;i<vnum();i++){
    			if(!isVisited[i]){
    				core = i;
    				break;
    			}
    		}
    		
    		if(core==-1){
    			con = false;
    		}
    		else{
    			boolean isTree = true;
    			ArrayDeque<Integer> s = new ArrayDeque<>();
    			s.offerFirst(core);
    			isVisited[core] = true;
    			
    			while(!s.isEmpty()){
    				int now = s.pollFirst();
    				
    				for(int i:this.nextList(now)){
    					
    					if(isVisited[i]){
    						if(par[now] != i){
        						isTree = false;
    						}
    					}
    					else{
        					s.offerFirst(i);
        					isVisited[i] = true;
        					par[i] = now;
    					}
    				}

    			}
    			
    			if(isTree){
    				TreeNum += 1;
    			}
    		}
    	}
    	
    	return TreeNum;
	}
	
	//森かどうか返す
	boolean isForest(){
    	boolean[] isVisited = new boolean[vnum()];
    	int[] par = new int[vnum()];
    	
    	boolean con = true;
    	
    	while(con){
    		int core = -1;
    		
    		for(int i=0;i<vnum();i++){
    			if(!isVisited[i]){
    				core = i;
    				break;
    			}
    		}
    		
    		if(core==-1){
    			con = false;
    		}
    		else{
    			boolean isTree = true;
    			ArrayDeque<Integer> s = new ArrayDeque<>();
    			s.offerFirst(core);
    			isVisited[core] = true;
    			
    			while(!s.isEmpty()){
    				int now = s.pollFirst();
    				
    				for(int i:this.nextList(now)){
    					
    					if(isVisited[i]){
    						if(par[now] != i){
        						isTree = false;
    						}
    					}
    					else{
        					s.offerFirst(i);
        					isVisited[i] = true;
        					par[i] = now;
    					}
    				}

    			}
    			
    			if(!isTree){
    				return false;
    			}
    		}
    	}
    	
    	return true;
	}
	
	//連結成分数を返す
	int CCNum(){
    	boolean[] isVisited = new boolean[vnum()];
    	int CNum = 0;
    	
    	boolean con = true;
    	
    	while(con){
    		int core = -1;
    		
    		for(int i=0;i<vnum();i++){
    			if(!isVisited[i]){
    				core = i;
    				break;
    			}
    		}
    		
    		if(core==-1){
    			con = false;
    		}
    		else{

    			ArrayDeque<Integer> s = new ArrayDeque<>();
    			s.offerFirst(core);
    			isVisited[core] = true;
    			CNum += 1;
    			
    			while(!s.isEmpty()){
    				int now = s.pollFirst();
    				
    				for(int i:this.nextList(now)){
    					
    					if(!isVisited[i]){
        					s.offerFirst(i);
        					isVisited[i] = true;
    					}

    				}

    			}

    		}
    	}
    	
    	return CNum;
	}

	//連結成分に分割
	LinkedList<SGraph> CCSet(){
		LinkedList<SGraph> set = new LinkedList<>();
		
    	boolean[] isVisited = new boolean[vnum()];

    	boolean con = true;
    	
    	while(con){
    		int core = -1;
    		
    		for(int i=0;i<vnum();i++){
    			if(!isVisited[i]){
    				core = i;
    				break;
    			}
    		}
    		
    		if(core==-1){
    			con = false;
    		}
    		else{
    			java.util.ArrayList<Integer> list = new java.util.ArrayList<>();
    			ArrayDeque<Integer> s = new ArrayDeque<>();
    			s.offerFirst(core);
    			list.add(core);
    			isVisited[core] = true;
    			
    			while(!s.isEmpty()){
    				int now = s.pollFirst();
    				
    				for(int i:this.nextList(now)){
    					
    					if(!isVisited[i]){
        					s.offerFirst(i);
        					isVisited[i] = true;
        					list.add(i);
    					}
    				}

    			}
    			
    			Collections.sort(list);;
    			int size = list.size();
    			SGraph g = new SGraph(size);
    			
    			int[] newindex = new int[this.vnum()];
    			
    			for(int i=0;i<list.size();i++){
    				newindex[list.get(i)] = i;
    			}
    			
    			for(int i:list){
    				for(int j:this.nlist[i]){
    					if(i<j){
        					g.addEdge(newindex[i],newindex[j]);
    					}
    				}
    			}
    			
    			set.add(g);
    			
    		}
    	}
    	
    	return set;
	}

	//2点間距離をBFSで求める。到達不可は-1。
	int distance(int n, int m){
		
		ArrayDeque<Integer> q = new ArrayDeque<>();
		int[] d = new int[vnum()];	//nとの距離。未チェックなら-1。
		for(int i=0;i<vnum();i++){
			d[i] = -1;
		}
		
		q.add(n);
		d[n] = 0;
		
		while(!q.isEmpty()){
			int now = q.pollFirst();
			
			for(int i:nextList(now)){
				if(d[i] == -1){
					if(i==m){
						return d[now]+1;
					}
					
					d[i] = d[now]+1;
					q.offerLast(i);
				}
			}
		}
		
		return -1;
	}
	
	//nとの距離のリストを返す（BFS）。到達不可は-1。
	int[] distanceList(int n){
		
		ArrayDeque<Integer> q = new ArrayDeque<>();
		int[] d = new int[vnum()];	//nとの距離。未チェックなら-1。
		for(int i=0;i<vnum();i++){
			d[i] = -1;
		}
		
		q.add(n);
		d[n] = 0;
		
		while(!q.isEmpty()){
			int now = q.pollFirst();
			
			for(int i:nextList(now)){
				if(d[i] == -1){
					d[i] = d[now]+1;
					q.offerLast(i);
				}
			}
		}
		
		return d;
	}
	
	//2部グラフかどうか判定
	boolean isBipartite(){
		//白黒で2彩色可能か判定
		boolean[] isBlack = new boolean[vnum()];
		boolean[] isChecked = new boolean[vnum()];
		ArrayDeque<Integer> q = new ArrayDeque<>();
		
		boolean con = true;
		
		while(con){
			
			int core = -1;
			for(int i=0;i<vnum();i++){
				if(!isChecked[i]){
					core = i;
				}
			}
			
			if(core!=-1){
				q.offerFirst(core);
				isBlack[core] = true;
				isChecked[core] = true;
				
				while(!q.isEmpty()){
					int now = q.pollFirst();
					
					for(int i:nextList(now)){
						if(!isChecked[i]){
							isChecked[i] = true;
							isBlack[i] = !isBlack[now];
							q.offerFirst(i);
						}
						else{
							if(isBlack[i] == isBlack[now]){
								return false;
							}
						}
					}
				}	
			}
			else{
				con = false;
			}	
			
		}
	
		return true;
	}
	
	//2部グラフにしたときの、左右の頂点数のうち小さい方を返す（連結前提、不可能なら-1を返す）
	int bipartiteNum(){
		//白黒で2彩色可能か判定
		boolean[] isBlack = new boolean[vnum()];
		boolean[] isChecked = new boolean[vnum()];
		ArrayDeque<Integer> q = new ArrayDeque<>();
		
		q.offerFirst(0);
		isBlack[0] = true;
		isChecked[0] = true;
		
		while(!q.isEmpty()){
			int now = q.pollFirst();
			
			for(int i:nextList(now)){
				if(!isChecked[i]){
					isChecked[i] = true;
					isBlack[i] = !isBlack[now];
					q.offerFirst(i);
				}
				else{
					if(isBlack[i] == isBlack[now]){
						return -1;
					}
				}
			}
		}	
	
		//ここに到達すれば二部グラフ
		int blacknum = 0;
		for(int i=0;i<vnum();i++){
			if(isBlack[i]){
				blacknum += 1;
			}
		}
		
		return Math.min(blacknum, vnum()-blacknum);
	}

	//橋を列挙（連結グラフ）（indexは小→大）
	public ArrayList<EdgePair> bridge(){
		int[] ord = new int[vnum()];
		int[] ordidx = new int[vnum()]; //そのオーダーを持つ頂点のインデックス
		int[] lowlink = new int[vnum()];
		Arrays.fill(lowlink, -1);
		
		//DFS木を作り、ordを求める
		ArrayDeque<Integer> a = new ArrayDeque<>();
		a.offerFirst(0);
		int noword = 0;
		boolean isVisited[] = new boolean[vnum()];
		int parent[] = new int[vnum()];
		HashSet<EdgePair> tree = new HashSet<>(); //DFS木に含まれる辺（ここになければ後退辺
		
		while(!a.isEmpty()){
			int now = a.pollFirst();
			
			if(isVisited[now]){
				continue;
			}
			isVisited[now] = true;
			tree.add(new EdgePair(parent[now],now));
			
			ord[now] = noword;
			ordidx[noword] = now;
			noword++;
			
			for(int i:nextList(now)){
				a.offerFirst(i);
				parent[i] = now;
			}
		}
		
		//後ろからlowlinkを求める
		for(int i=vnum()-1;i>=0;i--){
			int now = ordidx[i];
			int min = i;
			for(int j:nextList(now)){
				if(ord[j]<i){	//jが親
					if(tree.contains(new EdgePair(j,now))){ //後退辺でないなら数えない
						continue;
					}
				}
				if(lowlink[j]!=-1){
					if(min>lowlink[j]){
						min = lowlink[j];
					}
				}
				else{
					if(min>ord[j]){
						min = ord[j];
					}
				}
			}
			lowlink[now] = min;
		}
		
		ArrayList<EdgePair> ans = new ArrayList<>();
		
		//全ての辺が橋かチェック
		for(int i=0;i<vnum();i++){
			for(int j:nextList(i)){
				if(ord[i]<ord[j]){ //iが親のときのみ調べる（2重に調べるのを防ぐ）
					if(ord[i] < lowlink[j]){
						ans.add(new EdgePair(Math.min(i,j),Math.max(i,j)));
					}
				}
			}
		}
		
		return ans;
	}
	
	class EdgePair implements Comparable<EdgePair>{
		int a,b;
		
		public EdgePair(int a, int b){
			this.a = a;
			this.b = b;
		}
		
		@Override
		public boolean equals(Object o){
			if(o instanceof EdgePair){
				EdgePair p = (EdgePair) o;
				return (a == p.a && b == p.b)||(a == p.b && b == p.a);
			}
			return super.equals(o);
		}
		
		@Override
		public int compareTo(EdgePair o){
			if(a!=o.a){
				return Integer.compare(a,o.a);
			}
			return Integer.compare(b, o.b);
		}
		
		@Override
		public int hashCode(){
			return (a<<16)+b;
		}
		
	}
	class NodeList extends ArrayList<Integer>{
		private static final long serialVersionUID = -4461479015945373120L;
	}
}


class FastScanner {
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;
	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		} else {
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) {
				return false;
			}
		}
		return true;
	}
	private int readByte() {
		if (hasNextByte())
			return buffer[ptr++];
		else
			return -1;
	}
	private static boolean isPrintableChar(int c) {
		return 33 <= c && c <= 126;
	}
	public boolean hasNext() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr]))
			ptr++;
		return hasNextByte();
	}
	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while (isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	public long nextLong() {
		if (!hasNext())
			throw new NoSuchElementException();
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}
	public int nextInt() {
		long nl = nextLong();
		if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
			throw new NumberFormatException();
		return (int) nl;
	}
	public double nextDouble() {
		return Double.parseDouble(next());
	}
}