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 <cmath>
#include <cstdlib>
#include <iostream>
#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>
#include <chrono>
#include <random>
#include <tuple>
#include <utility>
#include <fstream>

const long INF = (1l << 30);
const long LINF = (1l << 60);

typedef std::pair<long, long> P;

long v, e;
std::vector<long> edge[100005];
long depth[100005], lowlink[100005];
std::vector<P> ans;

void dfs(long par, long vis){
  for(int i = 0; i < edge[vis].size(); i++){
    long nx = edge[vis][i];
    if(depth[nx] == LINF){
      lowlink[nx] = depth[nx] = depth[vis]+1;
      dfs(vis, nx);
      lowlink[vis] = std::min(lowlink[vis], lowlink[nx]);
    }else{
      if(nx != par){
        lowlink[vis] = std::min(lowlink[vis], depth[nx]);
      }
    }
  }
}

int main(){
  scanf("%ld%ld", &v, &e);
  for(int i = 0; i < e; i++){
    long a, b;
    scanf("%ld%ld", &a, &b);
    edge[a].push_back(b);
    edge[b].push_back(a);
  }
  for(int i = 0; i < v; i++){
    depth[i] = lowlink[i] = LINF;
  }
  depth[0] = lowlink[0] = 0;
  dfs(0, 0);
  /*
  for(int i = 0; i < v; i++){
    printf("%ld (%ld,%ld)\n", i, depth[i], lowlink[i]);
  }
  //*/
  for(long i = 0; i < v; i++){
    for(int j = 0; j < edge[i].size(); j++){
      long k = edge[i][j];
      if(depth[i] < lowlink[k]){
        ans.push_back(P(std::min(i, k), std::max(i, k)));
      }
    }
  }
  std::sort(ans.begin(), ans.end());
  for(int i = 0; i < ans.size(); i++){
    printf("%ld %ld\n", ans[i].first, ans[i].second);
  }
}