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:
//In the name of Allah
#include <bits/stdc++.h>

using namespace std;
const int maxn=100005,inf=200000;
int n,m,mark[maxn],par[maxn],high[maxn],mini[maxn],minimomesh[maxn],dp[maxn],mark2[maxn];
vector<int> adj[maxn];
vector<pair<int,int>> v;
pair<int ,int > kol[maxn];
void dfs(int v)
{
    mark[v]=1;

    for(int u=0; u<adj[v].size(); u++)
    {
        int r=adj[v][u];
        if(mark[r]==0)
        {


            par[r]=v;
            high[r]=high[v]+1;

            dfs(r);
           // dp[v]=min(dp[r],dp[v]);




        }

    }




}
void dfs2(int v)
{
    mark2[v]=1;


    for(int c=0; c<adj[v].size(); c++)
    {
        int z=adj[v][c];
        if(mark2[z]==0)
        {
            dfs2(z);
            dp[v]=min(dp[z],dp[v]);
        }
    }

}
void minyab(int v)
{
    dp[v]=inf;
    for(int e=0; e<adj[v].size(); e++)
    {
        int t=adj[v][e];
        if(t!=par[v])
        {


        dp[v]=min(high[t],dp[v]);
    }
    }
    return;
}


int main()
{


    cin>>n>>m;
    for(int i=0; i<m; i++)
    {
        int x,y;
        cin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    dfs(0);

    for(int i=0; i<n; i++)
    {
       minyab(i);

    }
    dfs2(0);


  /*  for(int i=0; i<n; i++)
    {
        cout<<mini[i]<<' '<<high[i]<<' '<<high[par[i]]<<' '<<dp[i]<<' '<<minimomesh[i]<<endl;
    }*/

    for(int i=1; i<n; i++)
    {
        if(dp[i]>high[par[i]])
        {


            kol[i].first=i;
            kol[i].second=par[i];
            if(kol[i].first>kol[i].second)
            {
                swap(kol[i].first,kol[i].second);
            }
            v.push_back(kol[i]);
        }
    }
    sort(v.begin(),v.end());
    for(int i=0;i<v.size();i++)
    {
        cout<<v[i].first<<' '<<v[i].second<<endl;
    }





    return 0;
}