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:
import sys
from typing import List, Set


sys.setrecursionlimit(200000)


def dfs(cur : int, prev: int) -> None:
    global prenum, parent, lowest, counter, bridges
    prenum[cur] = lowest[cur] = counter
    counter += 1
    for edge in edges[cur]:
        if prenum[edge] != sys.maxsize:
            if edge != prev:
                lowest[cur] = min(lowest[cur], prenum[edge])
            continue
        parent[edge] = cur
        dfs(edge, cur)
        lowest[cur] = min(lowest[cur], lowest[edge])
    if prenum[cur] == lowest[cur]:
        bridges.add((cur, prev) if cur < prev else (prev, cur))


if __name__ == "__main__":
    V, E = map(int, input().split())
    edges: List[Set[int]] = [set() for _ in range(V)]

    for _ in range(E):
        s, t = map(int, input().split())
        edges[s].add(t)
        edges[t].add(s)

    prenum = [sys.maxsize] * V
    parent = [sys.maxsize] * V
    lowest = [sys.maxsize] * V
    counter = 0
    bridges = set()  # type: ignore

    dfs(0, -1)
    for bridge in sorted(bridges)[1:]:
        print(*bridge)