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 rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++)
#define debug(x) cerr<<#x<<":"<<x<<endl
const int maxn=(int)1e6+5;
int low[maxn];
int vis[maxn],lv[maxn];
vector<int> E[maxn];
set<pair<int,int> > bridge;
map<pair<int,int>,int> V;
/* 
1.if there are parellel lines, can't use fa.

 */
void dfs(int now,int curlv,int fa){
    low[now]=curlv;
    lv[now]=curlv;
    vis[now]=1;
    int son_cnt=0;
    for(auto v:E[now]){
        //1.tree edge to fa, or back edge visited by now's descendant
        if(v==fa)continue;
        //2.back edge to now's ancestor
        if(vis[v]) low[now]=min(low[now],lv[v]);
        //3.tree edge to son.
        else{
            son_cnt++;
            dfs(v,curlv+1,now);
            low[now]=min(low[now],low[v]);
            if(low[v]>lv[now]){
                bridge.insert({min(now,v),max(now,v)});
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,m;
    cin>>n>>m;
    rep(i,1,m){
        int x,y;
        cin>>x>>y;
        E[x].push_back(y);
        E[y].push_back(x);
    }
    rep(i,0,n-1)if(!vis[i])dfs(i,0,-1);
   // rep(i,0,n-1)debug(i),debug(low[i]);
    for(auto e:bridge)cout<<e.first<<' '<<e.second<<endl;
}
/* 
4 4
0 1
0 2
1 2
2 3
 */