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>

#define MAX 100000

std::vector<int>Graph[MAX];
bool visited[MAX];

int N;

int prenum[MAX], parent[MAX], lowest[MAX], timer;

struct compare {
    bool operator() (const std::pair<int,int> &lhs, const std::pair<int,int> &rhs) const{
        if (lhs.first == rhs.first) return lhs.second < rhs.second;
        return (lhs.first < rhs.first);
    }
};

std::set<std::pair< int, int>, compare > bridges;

void dfs(int current, int prev) {

    prenum[current] = lowest[current] = timer;
    timer++;

    visited[current] = true;

    int next;

    for (int i = 0; i < Graph[current].size(); i++) {
        next = Graph[current][i];
        if (!visited[next]) {
            parent[next] = current;
            dfs(next, current);

            lowest[current] = std::min(lowest[current], lowest[next]);
            
            if (lowest[next] > prenum[current]) {
                if (next > current) bridges.insert({current, next});
                else bridges.insert({next, current});

            }


        }
        else if (prev != next) {
            lowest[current] = std::min(lowest[current], prenum[next]);
        }
    }
}

void bridge() {
    for (int i = 0; i < N; i++) visited[i] = false;

    timer = 1;

    dfs(0, -1); //0 == root

    for(std::set< std::pair<int, int> >::iterator it = bridges.begin(); it != bridges.end(); it++) {
        std::cout << it->first << " " << it->second << std::endl;
    }
}


int main()
{
    int Edges;
    std::scanf("%d %d", &N, &Edges);

    int start, target;

    for (int i = 0; i < Edges; i++) {
        std::scanf("%d %d", &start, &target);
        Graph[start].push_back(target);
        Graph[target].push_back(start);
    }

    bridge();


    return 0;
}