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 PYTHON3):

Solution:
# Undirected Graph


class Edge:
    __slots__ = ('v', 'w')

    def __init__(self, v, w):
        self.v = v
        self.w = w

    def either(self):
        return self.v

    def other(self, v):
        if v == self.v:
            return self.w
        else:
            return self.v


class Graph:
    def __init__(self, v):
        self.v = v
        self._edges = [[] for _ in range(v)]

    def add(self, e):
        self._edges[e.v].append(e)
        self._edges[e.w].append(e)

    def adj(self, v):
        return self._edges[v]

    def edges(self):
        for es in self._edges:
            for e in es:
                yield e


def bridges(graph):
    def visit(v, e):
        nonlocal n
        w = e.other(v)
        if not visited[w]:
            parent[w] = v
            n += 1
            visited[w] = n
            low[w] = n
            return True
        elif w != parent[v]:
            low[v] = min(low[v], visited[w])
            return False

    def leave(p, e):
        c = e.other(p)
        if p == parent[c] and low[c] > visited[p]:
            es.append(e)
        low[p] = min(low[p], low[c])
        return False

    visited = [0] * graph.v
    low = [0] * graph.v
    parent = [-1] * graph.v
    es = []

    s = 0
    n = 1
    visited[s] = n
    low[s] = n
    stack = [(s, e, visit) for e in graph.adj(s)]

    while stack:
        v, e, func = stack.pop()
        # print(v, e.v, e.w, func.__name__, visited, low)
        if func(v, e):
            stack.append((v, e, leave))
            w = e.other(v)
            for ne in graph.adj(w):
                stack.append((w, ne, visit))

    return es


def run():
    v, e = [int(i) for i in input().split()]
    g = Graph(v)

    for _ in range(e):
        s, t = [int(i) for i in input().split()]
        g.add(Edge(s, t))

    edges = [(e.v, e.w) if e.v < e.w else (e.w, e.v)
             for e in bridges(g)]

    for v, w in sorted(edges):
        print(v, w)


if __name__ == '__main__':
    run()