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;
#define int long long
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) x.begin(),x.end()
#define dmp(x) cerr<<#x<<":"<<x<<endl
typedef pair<int,int> P;
typedef pair<int,P> PP; 
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
const int MOD = 1e9+7;

vector<int> g[111111];
vector<P> bs;
vector<int> pre(111111,-1),low(111111,-1);
int t;

int dfs(int x=0,int p=-1){
  if(pre[x]!=-1)return pre[x];
  low[x]=pre[x]=t++;
  for(int i=0;i<g[x].size();i++){
    if(g[x][i]==p)continue;
    low[x]=min(low[x],dfs(g[x][i],x));
  }
  if(p!=-1&&low[x]==pre[x]){
    if(p<x)swap(p,x);
    bs.pb(P(x,p));
  }
  return low[x];
}

signed main(){
  int v,e;
  cin>>v>>e;
  for(int i=0;i<e;i++){
    int s,t;
    cin>>s>>t;
    g[s].pb(t);
    g[t].pb(s);
  }
  dfs();
  sort(all(bs));
  for(auto a:bs)cout<<a.fi<<" "<<a.se<<endl;
  return 0;
}