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<vector>
#include<algorithm>
using namespace std;
const int MAXN=1000005;
const int MAXE=1000005;
typedef pair<int,int> ii;
vector <int> adj[MAXN];
ii ec[MAXE];
int prof[MAXN],low[MAXN],padre[MAXN],cont,N,M,a,b,nec;
bool usa[MAXN];
void bridge(int v){
    int child=0; //contara el n??mero de hijos en el DFST (DFS Tree)
    usa[v]=true;
    //low nos dice el ancestro m??s alto al que apunta alguno de los descendientes de v en DFST
    //prof nos dice en que tiempo se visitaron los nodos en el DFS
    low[v]=prof[v]=++cont;
    for (int i=0; i<(int)adj[v].size(); i++){
        int w=adj[v][i];
        if (!usa[w]){
            child++;
            padre[w]=v;
            bridge(w);
            low[v]=min(low[v],low[w]);
            //(v,w) ser?? una arista de corte si:
            //no podemos alcanzar a ninguno de los ancestros
            //de v o a v desde el ??rbol enraizado en w
            if (low[w]>prof[v])ec[nec++]=make_pair(min(v,w),max(v,w));
        } else if(w!=padre[v]) low[v]=min(low[v],prof[w]);
    }
}
int main()
{
    //Asumimos que el grafo es conexo, no dirigido y simple
    //En caso de no ser conexo lo hacemos para cada componente conexa
    scanf("%d%d",&N,&M);
    for (int i=0; i<M; i++){
        scanf("%d%d",&a,&b);
        adj[a].push_back(b); adj[b].push_back(a);
    }
    //Inicializamos los padres
    fill(padre,padre+N,-1);
    //En caso de ser multicaso inicializar prof,low,usa,ec,nec
    bridge(0);
    //ordenamos los puentes para mostrarlas en orden
    sort(ec,ec+nec);
    //en ec tenemos los puentes
    for (int i=0; i<nec; i++)printf("%d %d\n",ec[i].first,ec[i].second);
    return 0;
}