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<algorithm>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
using namespace std;
#define MON 1000000007
#define INF (1<<29)
typedef long long Int;
typedef pair<Int, Int> P;

#define max(x, y) ((x)>(y)?(x):(y))
#define min(x, y) ((x)<(y)?(x):(y))

class Edge{
public:
  int from, to, rev;
  Int cost, lim;
  Edge(int from, int to, Int cost, int lim = -1, Int rev = -1):
    from(from),to(to),cost(cost),lim(lim),rev(rev){}
};


class Graph{
public:
  int n;
  int m;
  vector<vector<Edge>> edge;
  Graph(int n = 0):n(n),m(0){
    edge = vector<vector<Edge>>(n);
  }
  void add_edge(int from, int to, int cost = 1, int lim = -1)
  {
    if(lim == -1){
      edge[from].push_back(Edge(from, to, cost));
      return;
    }
    edge[from].push_back(Edge(from, to, cost, lim, edge[to].size()));
    edge[to].push_back(Edge(to, from, -cost, 0, edge[from].size() - 1));
  }
};

int n, m, s, t;
Graph g;
vector<int> come(108000);
vector<int> ongo(108000);
vector<int> cnt(108000);
vector<P> ans;
void dfs(int x, int last = - 1){
  come[x] = true;
  ongo[x] = true;
  for(auto e:g.edge[x]){
    if(e.to == last)continue;
    if(ongo[e.to]){
      cnt[x]++;
      cnt[e.to]--;
    }
    if(!come[e.to]){
      dfs(e.to, x);
      cnt[x] += cnt[e.to];
    }
  }
  ongo[x] = false;
  if(last != -1 && cnt[x] == 0){
    ans.push_back(P(min(x, last), max(x, last)));
  }
}

int main(){
  cin >> n >> m;
  g = Graph(n);
  for(int i = 0;i < m;i++){
    cin >> s >> t;
    g.add_edge(s, t);
    g.add_edge(t, s);
  }
  dfs(0);
  sort(ans.begin(), ans.end());
  for(auto p:ans)cout << p.first << " " << p.second << endl;
  return 0;
}