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 <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <utility>
#include <map>
#include <string>
#define maxn 100005
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int n,m;
int dfn[maxn],low[maxn],ind;
vector <int> adj[maxn];
vector <P> ans;
void tarjan(int u,int f){
  dfn[u] = low[u] = ++ind;
  for(int i=0;i<adj[u].size();i++){
    int v = adj[u][i];
      if(dfn[v] == 0){
        tarjan(v,u);
        low[u] = min(low[u],low[v]);
      }else if(v != f){
        low[u] = min(low[u],dfn[v]);
      }
  }
  if(dfn[u] == low[u]){
  	if(u >= f) swap(u,f);
  	if(u != -1) ans.push_back(mp(u,f));
  }
}
int main(){
  scanf("%d%d",&n,&m);
  for(int i=1;i<=m;i++){
  	int u,v;
  	scanf("%d%d",&u,&v);
  	adj[u].push_back(v);
  	adj[v].push_back(u);
  }
  for(int i=0;i<n;i++){
  	if(dfn[i] == 0) tarjan(i,-1);
  }
  sort(ans.begin(),ans.end());
  for(int i=0;i<ans.size();i++){
  	printf("%d %d\n",ans[i].first,ans[i].second);
  }
  return 0;
}