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<iostream>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;
const int maxn = 100001;

vector<int> G[maxn];
struct Edge
{
    int u, v;
};

vector<Edge> ans;
bool cmp(Edge a, Edge b)
{
    if(a.u != b.u)
        return a.u < b.u;
    else
        return a.v < b.v;
}
int n, e;
int prenum[maxn], parent[maxn], lowest[maxn], vis[maxn];
int cnt;
void dfs(int i,int Father)
{
    parent[i]=Father;
    prenum[i]=lowest[i]=cnt++;
    for(int j=0;j<G[i].size();++j)
    {
        int k=G[i][j];
        if(prenum[k]==-1)
        {
            dfs(k,i);
            lowest[i]=min(lowest[i],lowest[k]);
        }
        else if(Father!=k)
            lowest[i]=min(lowest[i],prenum[k]);
    }
}

void bridge()
{
    for(int i = 0; i < n; i++)
        prenum[i] = -1;
    cnt = 0;
    parent[0] = -1;
    dfs(0, -1);
    int rootCnt = 0;

    for(int i = 1; i < n; i++)
    {
        int p = parent[i];
        if(p == 0) rootCnt++;
        if(prenum[p] < lowest[i])
        {
            Edge e;
            if(p < i)
            {
                e.u = p;
                e.v = i;
            }
            else
            {
                e.u = i;
                e.v = p;
            }
            ans.push_back(e);
        }
    }

    sort(ans.begin(), ans.end(), cmp);
    for(int i = 0; i < ans.size(); i++)
        cout << ans[i].u << " " << ans[i].v << endl;
}

int main()
{
    cin >> n >> e;
    for(int i = 0; i < e; i++)
    {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    bridge();
    return 0;
}