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;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pint;

const int max_n=100001;
vector<int> vi[max_n];
vector<pint> bridge;
vector<int> articulation;
int ord[max_n],low[max_n];
bool used[max_n];
void lowlink_dfs(int v,int par,int &cur_ord){
    used[v]=true;
    ord[v]=cur_ord++;
    low[v]=ord[v];

    bool isArticulation=false;
    int ctree=0;
    rep(i,vi[v].size()){
        if(!used[vi[v][i]]){
            ++ctree;
            lowlink_dfs(vi[v][i],v,cur_ord);
            low[v]=min(low[v],low[vi[v][i]]);
            if(par!=-1&&ord[v]<=low[vi[v][i]]) isArticulation=true;
            if(ord[v]<low[vi[v][i]]) bridge.pb(mp(min(v,vi[v][i]),max(v,vi[v][i])));
        }
        else if(vi[v][i]!=par){
            low[v]=min(low[v],ord[vi[v][i]]);
        }
    }
    if(par==-1&&ctree>1) isArticulation=true;
    if(isArticulation) articulation.pb(v);
}
int main(){
    int n,m,sr,ds;
    cin>>n>>m;
    rep(i,m){
        cin>>sr>>ds;
        vi[sr].pb(ds);
        vi[ds].pb(sr);
    }
    int ord=0;
    rep(i,n){
        if(!used[i]) lowlink_dfs(i,-1,ord);
    }
    sort(bridge.begin(),bridge.end());
    /*rep(i,articulation.size()){
        cout<<articulation[i]<<endl;
    }*/
    rep(i,bridge.size()){
        cout<<bridge[i].first<<" "<<bridge[i].second<<endl;
    }
    return 0;
}