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;

// ord := rootを0とした時、DFSを行った時の順序番号
// lowlink := 頂点vからDFS木の葉方向の辺を0回以上、後退辺を0回以上1回以下通っていける頂点のordの最小値

vector<int> G[100010];
vector<pair<int, int>> bridge;
vector<int> Articulation;
int ord[100010], lowlink[100010];
bool visited[100010];
void dfs(int v, int p, int &k)
{
  visited[v] = true;

  ord[v] = k++;
  lowlink[v] = ord[v];

  bool isArticulation = false;
  int ct = 0;

  for (int i = 0; i < G[v].size(); i++)
  {
    if (!visited[G[v][i]])
    {
      ct++;
      dfs(G[v][i], v, k);
      lowlink[v] = min(lowlink[v], lowlink[G[v][i]]);

      if (~p && ord[v] <= lowlink[G[v][i]])
        isArticulation = true;

      if (ord[v] < lowlink[G[v][i]])
        bridge.push_back(make_pair(min(v, G[v][i]), max(v, G[v][i])));
    }
    else if (G[v][i] != p)
    {
      lowlink[v] = min(lowlink[v], ord[G[v][i]]);
    }
  }

  //根の場合子が一つなら関節点ではなく、そうでなければ関節点
  if (p == -1 && ct > 1)
    isArticulation = true;

  if (isArticulation)
    Articulation.push_back(v);
}
int main()
{
  int n, m;
  cin >> n >> m;

  for (int i = 0; i < m; i++)
  {
    int x, y;
    cin >> x >> y;
    G[x].push_back(y);
    G[y].push_back(x);
  }

  int k = 0;
  for (int i = 0; i < n; i++)
  {
    if (!visited[i])
      dfs(i, -1, k);
  }

  sort(bridge.begin(), bridge.end());
  for (int i = 0; i < bridge.size(); i++)
  {
    cout << bridge[i].first << " " << bridge[i].second << endl;
  }
  return 0;
}

// Varify
// 関節点の列挙: 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
// 参考
// npca2014年部誌 競技プログラミングで使えるグラフ理論の基本
// http://kagamiz.hatenablog.com/entry/2013/10/05/005213