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 maxn 100005
vector<pair<int, int> > vp;
int vis[maxn],low[maxn],dfn[maxn];
int ind ;
vector<int> g[maxn];
void tarjan(int u,int p)
{
    dfn[u]=low[u]=++ind;
    vis[u]=1;
    for(int i=0;i<g[u].size();i++)
    {
        int v=g[u][i];
        if(v==p) continue;
        if(!vis[v])
        {
            tarjan(v,u);
            low[u]=min(low[v],low[u]);
            if(dfn[u]<low[v]) {
                int a = u, b = v;
                if (a > b) swap(a, b);
                vp.push_back(make_pair(a, b));
            }
        }
        else low[u]=min(low[u],dfn[v]);
    }
}
int v,e;
int main()
{
    scanf("%d%d",&v,&e);
    for(int i=0;i<e;i++)
    {
        int s,t;
        scanf("%d%d",&s,&t);
        g[s].push_back(t);
        g[t].push_back(s);
    }
    tarjan(0,-1);
    sort(vp.begin(), vp.end());
    for (int i = 0; i < vp.size(); i++)
        printf("%d %d\n", vp[i].first, vp[i].second);
    return 0;
}