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

using P = pair<int, int>;

#define N 100004

vector<int> g[N], g0[N];

vector<int> vs;
int lab[N], prv[N];

void dfs(int v, int p) {
  prv[v] = p;
  vs.push_back(v);
  lab[v] = vs.size();
  for(int w : g[v]) {
    if(w == p) {
      continue;
    }
    if(lab[w]) {
      if(lab[v] < lab[w]) {
        g0[v].push_back(w);
      }
      continue;
    }
    dfs(w, v);
  }
}

int used[N], ap[N];
vector<P> bs;
vector<int> aps;
void construct(int n) {
  dfs(0, -1);

  used[0] = 1;
  bool first = true;
  for(int u : vs) {
    if(!used[u]) {
      // (u, p) is a bridge
      int p = prv[u];
      bs.push_back(u < p ? P(u, p) : P(p, u));
      if(g[u].size() > 1) ap[u] = 1;
      if(g[p].size() > 1) ap[p] = 1;
    }
    bool cycle = false;
    for(int v : g0[u]) {
      int w = v;
      while(w != u && !used[w]) {
        used[w] = 1;
        w = prv[w];
      }
      if(w == u) {
        cycle = true;
      }
    }
    if(cycle) {
      if(!first) ap[u] = 1;
      first = false;
    }
  }
  for(int i=0; i<n; ++i) {
    if(ap[i]) aps.push_back(i);
  }
}

int main() {
  int n, m;
  cin >> n >> m;
  for(int i=0; i<m; ++i) {
    int a, b; cin >> a >> b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  construct(n);
  sort(bs.begin(), bs.end());
  for(P &e : bs) {
    cout << e.first << " " << e.second << endl;
  }
  return 0;
}