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>
using namespace std;

vector<int> G[100010];
bool used[100010];
int par[100010];
int dep[100010];
int low[100010];

void dfs(int v,int p,int d){
    used[v] = true;
    par[v] = p;
    dep[v] = d;
    low[v] = d;
    for(int i = 0 ; i < G[v].size() ; i ++){
        if(G[v][i] == p)continue;
        if(used[G[v][i]]){
            low[v] = min ( low[v] , dep[G[v][i]] );
        }
        else {
            dfs(G[v][i],v,d+1);
            low[v] = min ( low[v] , low[G[v][i]] );
        }
    }
}

int main(){
    int V,E;
    int s[100010],t[100010];
    scanf("%d%d",&V,&E);
    for(int i = 0 ; i < E ; i ++){
        scanf("%d%d",&s[i],&t[i]);
        G[s[i]].push_back(t[i]);
        G[t[i]].push_back(s[i]);
        if(s[i] > t[i])swap(s[i],t[i]);
    }
    for(int i = 0 ; i < 100010 ; i ++){
        used[i] = false;
    }
    dfs(0,-1,0);
    
    vector<pair<int,int>> ans;
    for(int i = 0 ; i < E ; i ++){
        if(par[s[i]] == t[i]){
            if(low[s[i]] > dep[t[i]])ans.push_back(pair<int,int>(s[i],t[i]));
        }
        else if(par[t[i]] == s[i]){
            if(low[t[i]] > dep[s[i]])ans.push_back(pair<int,int>(s[i],t[i]));
        }
    }
    sort(ans.begin(),ans.end());
    for(int i = 0 ; i < ans.size() ; i ++){
        printf("%d %d%c",ans[i].first,ans[i].second,10);
    }
}