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:
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_B&lang=jp
// hos?????????????????????????????????
// lowlink????¨??????????????????§??????
// lowlink????¨??????????????????§????????????????????¢?????¨?????????????????????????????§
// http://kagamiz.hatenablog.com/entry/2013/10/05/005213??????????????????
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
vector<int> G[100000];
vector<P> bridge;
vector<int> articulation;
int ord[100000], low[100000];
bool vis[100000];
int v, e, s, t, k;
void dfs(int v, int p, int &k) {
    vis[v] = true;
    ord[v] = k++; low[v] = ord[v];
    bool isArticulation = false;
    int ct = 0;
    for (int i=0; i<G[v].size(); i++) {
        if (!vis[G[v][i]]) {
            ct++;
            dfs(G[v][i], v, k);
            low[v] = min(low[v], low[G[v][i]]);
            if (~p && ord[v] <= low[G[v][i]]) isArticulation = true;
            if (ord[v] < low[G[v][i]]) bridge.push_back(P(min(v, G[v][i]), max(v, G[v][i])));
        } else if (G[v][i] != p) {
            low[v] = min(low[v], ord[G[v][i]]);
        }
    }
    if (p == -1 && ct > 1) isArticulation = true;
    if (isArticulation) articulation.push_back(v);
}
int main() {
    scanf("%d%d",&v,&e);
    for (int i=0; i<e; i++) {
        scanf("%d%d",&s,&t);
        G[s].push_back(t); G[t].push_back(s);
    }
    if (v == 1) {
    } else {
        k = 0;
        for (int i=0; i<v; i++) {
            if (!vis[i]) dfs(i, -1, k);
        }
        sort(bridge.begin(), bridge.end());
        for (int i=0; i<bridge.size(); i++) printf("%d %d\n",bridge[i].first, bridge[i].second);
    }
}