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 <stdio.h>
#include <stack>
#include <bitset>
#include <utility>
#include <vector>
#include <set>
using namespace std;
typedef pair<int,int> pi;
#define F first
#define S second
#define MP make_pair
#define PB push_back
const int N=1e5+10;
int p[N],low[N],dep[N],t=0;
stack<int> s;
bitset<N>went,in,used;
vector<pi> graph[N];
void dfs(int now){
    in[now]=went[now]=true;
    low[now]=dep[now]=++t;
    s.push(now);
    for(int i=0;i<graph[now].size();i++)if(!used[graph[now][i].S]){
        used[graph[now][i].S]=true;
        if(!went[graph[now][i].F])dfs(graph[now][i].F);
        if(in[graph[now][i].F])low[now]=min(low[now],low[graph[now][i].F]);
    }
    if(low[now]==dep[now]){
        while(s.top()!=now){
            p[s.top()]=now;
            in[s.top()]=false;
            s.pop();
        }
        p[now]=now;
        s.pop();
        in[now]=false;
    }
    return ;
}
int main(){
    int n,m,l,r;
    set<pi> ans;
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        scanf("%d%d",&l,&r);
        graph[l].PB(MP(r,i));
        graph[r].PB(MP(l,i));
    }
    went.reset();
    in.reset();
    used.reset();
    for(int i=0;i<n;i++)if(!went[i])dfs(i);
    for(int i=0;i<n;i++)for(int j=0;j<graph[i].size();j++)if(p[i]!=p[graph[i][j].F]){
        if(i<graph[i][j].F)ans.insert(MP(i,graph[i][j].F));
        else ans.insert(MP(graph[i][j].F,i));
    }
    for(auto u:ans)printf("%d %d\n",u.F,u.S);
}