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;


struct LowLink {
    int n, pos;
    vector<vector<int>> G;
    vector<int> ord, low, par, ap;
    vector<pair<int, int>> brg;
    LowLink(int n) : n(n), pos(0), G(n), ord(n, -1), low(n), par(n, -1){}
    void addEdge(int u, int v){
        G[u].push_back(v);
        G[v].push_back(u);
    }
    void dfs(int v){
        ord[v] = low[v] = pos++;
        int dup = 0;
        for(int u : G[v]){
            if(u == par[v]){
                if(dup) low[v] = min(low[v], ord[u]);
                dup = 1;
                continue;
            }
            if(~ord[u]){
                low[v] = min(low[v], ord[u]);
                continue;
            }
            par[u] = v;
            dfs(u);
            low[v] = min(low[v], low[u]);
            if(ord[v] < low[u]) brg.emplace_back(minmax(u, v));
        }
    }
    void build(){
        for(int i = 0;i < n;++i) if(ord[i] < 0) dfs(i);
        vector<int > cnt(n, 0);
        for(int i = 0;i < n;++i){
            int p = par[i];
            if(p < 0) continue;
            if(par[p] < 0) cnt[p]++;
            else if(ord[p] <= low[i]) ap.push_back(p);
        }
        for(int i = 0;i < n;++i) if(cnt[i] > 1) ap.push_back(i);
        sort(begin(ap), end(ap));
        sort(begin(brg), end(brg));
        ap.erase(unique(begin(ap), end(ap)), end(ap));
    }
    bool isBridge(int u, int v){
        if(ord[u] > ord[v]) swap(u, v);
        return ord[u] < low[v];
    }
};


int V, E;


int main(){
    cin >> V >> E;
    LowLink G(V);
    for(int i = 0;i < E;++i){
        int s, t;
        cin >> s >> t;
        G.addEdge(s, t);
    }
    G.build();
    for(auto p : G.brg) cout << p.first << ' ' << p.second << endl;
    return 0;
}