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;

#include<bits/stdc++.h>
using namespace std;
using cost_t=int;

struct Edge {
    int from, to;
    cost_t cost;
    Edge(int from, int to, cost_t cost) : from(from), to(to), cost(cost) {}
};

using Edges = vector<Edge>;
using Graph = vector<Edges>;

Edges bridgesDetection(Graph& g){
    int n = g.size();
    vector<int> pre(n,-1);
    vector<int> low(n);
    Edges res;
    int k=0;
    function<int(int,int)> dfs=[&](int v,int prev){
        low[v] = pre[v];
        for(auto& e:g[v]){
            if(e.to==prev) continue;
            if(pre[e.to]==-1){
                pre[e.to] = k++;
                low[v] = min(low[v], dfs(e.to,v));
                if(pre[v]<low[e.to]) res.push_back(e);
            }
            else low[v] = min(low[v], pre[e.to]);
        }
        return low[v];
    };
    for(int i=0;i<n;i++){
        if(pre[i]==-1){
            pre[i]=k++;
            dfs(i,-1);
        }
    }
    return res;
}
int main(){
    int V,E;
    cin>>V>>E;
    Graph g(V);
    for(int i=0;i<E;i++){
        int s,t;
        cin>>s>>t;
        g[s].push_back(Edge(s,t,0));
        g[t].push_back(Edge(t,s,0));
    }
    auto res = bridgesDetection(g);
    auto cmp=[&](Edge lhs,Edge rhs){
        auto mP=[&](Edge e){
            return make_pair(min(e.from,e.to),max(e.from,e.to));
        };
        auto lP=mP(lhs),rP=mP(rhs);
        return lP<rP;
    };
    sort(res.begin(),res.end(),cmp);
    for(auto &e:res){
        cout<<min(e.from,e.to)<<" "<<max(e.from,e.to)<<endl;
    }
    return 0;
}