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<vector>
#include<algorithm>
using namespace std;
class LowLink{
private:
    vector<vector<int>> Graph;
    vector<bool> visited; 
    vector<int> order, low;

    void dfs(int u = 0 , int ord = 0, int par = -1){
        visited[u] = true;
        order[u] = ord;
        low[u] = ord;
        bool is_articulation = false;
        int deg = 0;
        for(int& v : Graph[u]){
            if(par == v) continue;
            if(visited[v] == false){
                deg++;
                dfs(v, ord+1, u);
                is_articulation |= (par != -1 && order[u] <= low[v]);
                low[u] = min(low[u], low[v]);
                if(order[u] < low[v]) bridge.emplace_back(make_pair(min(u, v), max(u,v)));
            } else {
                low[u] = min(low[u], order[v]);
            }
        }
        is_articulation |= (par == -1 && deg > 1);
        if(is_articulation) articulation.emplace_back(u);
    }
public:
    vector<int> articulation;
    vector<pair<int, int>> bridge;
    LowLink() = delete;
    LowLink(vector<vector<int>>& G) :  Graph(G){
        visited.assign(Graph.size(), false);
        order.resize(Graph.size());
        low.resize(Graph.size());
        dfs(); 
    }

    vector<int> get_articulation(){
        return articulation;
    }

    vector<pair<int,int>> get_bridge(){
        return bridge;
    }
};

#include<iostream>
int main(){
    int V, E, u, v;
    cin >> V >> E;
    vector<vector<int>> G(V);
    for(int i = 0; i < E; i++){
        cin >> u >> v;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }

    LowLink lowlink(G);
    auto bridges = lowlink.get_bridge();
    sort(bridges.begin(), bridges.end());
    for(auto& v : bridges){
        cout << v.first << " " << v.second << endl;
    }
}