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;

// TwoEdgeConnectedComponents + LowLink
struct TwoEdgeConnectedComponents {
  int n;
  vector<vector<int>> g;
  vector<int> ord, low, articulation;
  vector<bool> used;
  using P = pair<int, int>;
  vector<P> bridge;
  TwoEdgeConnectedComponents(int _n = 1) : n(_n), g(n) {}
  TwoEdgeConnectedComponents(vector<vector<int>> &_g) : n(_g.size()), g(_g) {
    build();
  }

  bool add(int from, int to) {
    g[from].push_back(to);
    g[to].push_back(from);
    return 1;
  }

  void build() {
    ord.assign(n, -1);
    low.assign(n, -1);
    int k = 0;
    for (int i = 0; i < n; ++i)
      if (ord[i] < 0) lowlinkdfs(i, -1, k);
  }
  void lowlinkdfs(int now, int par, int &k) {
    ord[now] = low[now] = k++;
    bool ch = 0;  // articulation
    int cnt = 0;
    for (auto &to : g[now])
      if (ord[to] < 0) {
        ++cnt;
        lowlinkdfs(to, now, k);
        low[now] = min(low[now], low[to]);
        ch |= ~par && low[to] >= ord[now];  // articulation
        if (ord[now] < low[to])
          bridge.emplace_back(min(now, to), max(now, to));  // bridge
      } else if (to != par)
        low[now] = min(low[now], ord[to]);
    ch |= par == -1 && cnt > 1;           // articulation
    if (ch) articulation.push_back(now);  // articulation
  }
};

long long n, m;
TwoEdgeConnectedComponents lowlink;
vector<vector<int>> g;

int main() {
  cin >> n >> m;
  g.resize(n);
  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  lowlink = TwoEdgeConnectedComponents(g);
  using P = pair<int, int>;

  vector<P> res = lowlink.bridge;
  sort(res.begin(), res.end());
  for (auto p : res) cout << p.first << " " << p.second << endl;
  return 0;
}