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,time;
    vector<int> ord,low;
    vector<vector<int>> G;
    vector<int> articulation;
    vector<pair<int,int>> bridge;
    Lowlink(int n):n(n),time(0),ord(n,-1),low(n),G(n){}
    void add_edge(int u,int v){
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    void dfs(int v,int p){
        ord[v]=low[v]=time++;
        bool is_articulation=false;
        int cnt=0;
        for (int u:G[v]){
            if (u==p) continue;
            if (~ord[u]){
                low[v]=min(low[v],ord[u]);
                continue;
            }
            ++cnt;
            dfs(u,v);
            low[v]=min(low[v],low[u]);
            is_articulation|=(~p&&ord[v]<=low[u]);
            if (ord[v]<low[u]) bridge.emplace_back(v,u);
        }
        is_articulation|=(p<0&&cnt>1);
        if (is_articulation) articulation.emplace_back(v);
    }
    void build(){
        for (int v=0;v<n;++v){
            if (ord[v]<0) dfs(v,-1);
        }
    }
};

// https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/3/GRL_3_A

void GRL_3_A(){
    int V,E; cin >> V >> E;
    Lowlink L(V);
    for (int i=0;i<E;++i){
        int s,t; cin >> s >> t;
        L.add_edge(s,t);
    }
    L.build();
    vector<int> ans=L.articulation;
    sort(ans.begin(),ans.end());
    for (int v:ans) cout << v << '\n';
}

// https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/3/GRL_3_B

void GRL_3_B(){
    int V,E; cin >> V >> E;
    Lowlink L(V);
    for (int i=0;i<E;++i){
        int s,t; cin >> s >> t;
        L.add_edge(s,t);
    }
    L.build();
    vector<pair<int,int>> ans=L.bridge;
    for (auto &e:ans) if (e.second<e.first)
        swap(e.first,e.second);
    sort(ans.begin(),ans.end());
    for (auto e:ans) cout << e.first << ' ' << e.second << '\n';
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    GRL_3_B();
}