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;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=100001,INF=1<<30;
vector<int> S[MAX];
int N,ord[MAX],low[MAX],visit[MAX],par[MAX],timer;

void DFS(int cur,int mae){
    
    ord[cur]=low[cur]=timer;
    par[cur]=mae;
    visit[cur]=1;
    timer++;
    
    for(int i=0;i<S[cur].size();i++){
        int a=S[cur][i];
        if(a==mae) continue;
        if(visit[a]){
            low[cur]=min(low[cur],ord[a]);
            continue;
        }
        DFS(a,cur);
        low[cur]=min(low[cur],low[a]);
    }
}

void search(int u){//u==0なら関節点、1なら橋
    for(int i=0;i<N;i++){
        visit[i]=0;
        par[i]=-1;
    }
    timer=1;
    
    DFS(0,-1);
    
    if(u==0){
        set<int> se;
        int cnt=0;
        for(int i=1;i<N;i++){
            if(par[i]==0) cnt++;
            else if(ord[par[i]]<=low[i]) se.insert(par[i]);
        }
        if(cnt>1) se.insert(0);
        
        for(auto it=se.begin();it!=se.end();it++){
            cout<<*it<<endl;
        }
    }else{
        set<pair<int,int>> se;
        for(int i=0;i<N;i++){
            for(int j=0;j<S[i].size();j++){
                int x=S[i][j];
                if(ord[i]<low[x]){
                    int a=i,b=x;
                    if(a>b) swap(a,b);
                    se.insert(make_pair(a,b));
                }
            }
        }
        
        for(auto it=se.begin();it!=se.end();it++){
            cout<<(*it).first<<" "<<(*it).second<<endl;
        }
    }
}

int main(){

    int M;cin>>N>>M;
    for(int i=0;i<M;i++){
        int a,b;cin>>a>>b;
        S[a].push_back(b);
        S[b].push_back(a);
    }
    
    search(1);
}