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:
/**
 * 関節点 : https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/3/GRL_3_A
 * 橋 : https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/3/GRL_3_B
 * */

#include <bits/stdc++.h>
using namespace std;
#define INF 1<<29
#define all(v) (v).begin(), (v).end()

int V, E; //頂点数 辺の数
vector<vector<int>> G(V); //頂点の隣接リスト
vector<int> ord_pre(V, INF); //行きがけ順の記録
vector<int> lowlink(V, INF); //lowlinkの記録
vector<pair<int, int>> Bridges; //橋のリスト
vector<int> ArticulationPoints; //関節点のリスト

int pre = 0; //行きがけ順序

void recdfs(int p, int u){ //p : uの親
  ord_pre[u] = pre++; //uの番号を確定する
  lowlink[u] = ord_pre[u];

  int cnt = 0; //DFS木次数カウント
  bool isArt = false; //関節点か否か

  for(int v: G[u]){ //uから行ける頂点vについて
    if(ord_pre[v]==INF){ //未訪問ならばuの子なので
      cnt++;

      recdfs(u, v); //uの子であるvの番号を確定させる //vのlowlinkも確定
      lowlink[u] = min(lowlink[u], lowlink[v]);

      if(ord_pre[u] < lowlink[v])Bridges.push_back({u,v}); //橋の判定してリストに入れる
      if(p!=-1 && ord_pre[u]<=lowlink[v])isArt = true; //根以外の関節点判定

    }else if( v != p ){
      //このとき uv が後退辺
      lowlink[u] = min(lowlink[u], ord_pre[v]);
    }
  }
  if(p==-1 && cnt>1)isArt = true; //根の関節点判定
  if(isArt)ArticulationPoints.push_back(u); //関節点だったらリストに入れる
}


int main(){
  cin>>V>>E;
  G.resize(V);
  for(int i=0; i<E; i++){
    int s,t;
    cin>>s>>t; //s--;t--;
    G[s].push_back(t);
    G[t].push_back(s);
  }

  ord_pre.assign(V, INF);
  lowlink.assign(V,INF);
  pre = 0;
  recdfs(-1, 0);

  /* 3a
  sort(all(ArticulationPoints));
  for(int x: ArticulationPoints)cout<<x<<endl;
  //*/

  //* 3b
  for(auto &x: Bridges){
    if(x.first>x.second)swap(x.first, x.second);
  }
  sort(all(Bridges));
  for(auto x: Bridges)cout<<x.first<<" "<<x.second<<endl;
  //*/
}