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:
class in{struct It{int it;const bool rev;explicit constexpr It(int it_, bool rev=false):it(it_),rev(rev){}int operator*(){return it;}bool operator!=(It& r){return it!=r.it;}void operator++(){rev?--it:++it;}};const It i,n;public:explicit constexpr in(int n):i(0),n(n<0?0:n){}explicit constexpr in(int i,int n):i(i,n<i),n(n){}const It& begin(){return i;}const It& end(){return n;}};
  
#include <iostream>
#include <vector>
#include <string>
#include <functional>
#include <algorithm>
using namespace std;
const int INF = 1e9;


int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n);
    for(int _ : in(m)) {
        int u, v;
        cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    vector<pair<int, int>> bridge;
    vector<int> depth(n, INF), ub(n, INF);
    function<void(int, int, int)> dfs = [&](int v, int p, int d) {
        depth[v] = d;
        ub[v] = d;
        for(int nv : adj[v]) {
            if(nv == p) continue;
            if(depth[nv] != INF) {
                ub[v] = min(ub[v], depth[nv]);
                continue;
            }
            dfs(nv, v, d + 1);
            ub[v] = min(ub[v], ub[nv]);
            if(ub[nv] > depth[v])
                bridge.emplace_back(min(v, nv), max(v, nv));
        }
    };
    dfs(0, -1, 0);
    sort(bridge.begin(), bridge.end());
    for(auto p : bridge) cout << p.first << ' ' << p.second << '\n';
    return 0;
}