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;
typedef pair<int,int>P;
struct Bridge{
  int n;
  vector<vector<int> > G;
  vector<int>low,used,depth;
  set<pair<int,int> >ans;
  Bridge(){}
  Bridge(int sz):n(sz),low(sz),used(sz),depth(sz),G(sz){}
  void add(int a,int b){
    G[a].push_back(b);
    G[b].push_back(a);
  }
  void dfs(int x,int d,int prev){
    depth[x]=d;
    for(int i=0;i<G[x].size();i++){
      int nx=G[x][i];
      if(nx==prev)continue;
      if(!used[nx]){
        used[nx]=true;
        dfs(nx,d+1,x);
        if(!low[nx]) ans.insert(P(min(x,nx),max(x,nx)));
        low[x]+=low[nx];
      }
      else if(d>depth[nx])low[nx]--,low[x]++;
    }
  }
  void build(){
    fill(used.begin(),used.end(),0);
    fill(low.begin(),low.end(),0);
    fill(depth.begin(),depth.end(),0);
    used[0]=1;
    dfs(0,0,0);
  }
  void prin(){
    set<P>::iterator it=ans.begin();
    while(it!=ans.end()){
      cout<< (*it).first <<' '<< (*it).second <<endl;
      it++;
    }
  }
};
int main(){
  int n,m,s,t;
  cin>>n>>m;
  Bridge B(n);
  for(int i=0;i<m;i++){
    cin>>s>>t;
    B.add(s,t);
  }
  B.build();
  B.prin();
  return 0;
}