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 <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;


class Lowlink{
public:
  // {v_from, v_to}
  vector<pair<int,int>> bridge;
  // [v]
  vector<int> articulation_point;
  void construct(const vector<vector<int>>& g){
    const int n = g.size();
    bridge = vector<pair<int, int>>{};
    articulation_point = vector<int>{};

    vector<int> ord(n, -1);
    vector<int> low(n);
    for(int i=0; i<n; i++){
      dfs(g, ord, low, i);
    }
  }

private:
  void dfs(
    const vector<vector<int>>& g, vector<int>& ord, vector<int>& low,
    int cur, int par = -1)
  {
    ord[cur] = par==-1 ? 0 : ord[par] + 1;
    low[cur] = ord[cur];
    int num_children = 0;
    bool is_articulation = false;
    for(auto& nex: g[cur]){
      if(ord[nex] == -1){
        ++num_children;
        dfs(g, ord, low, nex, cur);
        low[cur] = min(low[cur], low[nex]);
        if(ord[cur] <= low[nex] && par!=-1)
          is_articulation = true;
        if(ord[cur] < low[nex])
          bridge.emplace_back(min(cur, nex), max(cur, nex));
      }else if(nex != par){ // back edge
        low[cur] = min(low[cur], ord[nex]);
      }
    }
    if(par == -1 && num_children >= 2)
      is_articulation = true;
    if(is_articulation)
      articulation_point.push_back(cur);
  }

};

int main(){
  int n,e;
  cin >> n >> e;
  vector<vector<int>> g(n);
  for(int i=0; i<e; i++){
    int u,v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }

  Lowlink lowlink;
  lowlink.construct(g);
  auto b = lowlink.bridge;
  sort(begin(b), end(b));
  for(auto e : b){
    cout << e.first << " " << e.second << endl;
  }
  return 0;
}