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:
from sys import stdin
readline = stdin.readline


def main():
    v, e = map(int, readline().split())
    from collections import defaultdict
    g = defaultdict(list)

    for _ in range(e):
        s, t = map(int, readline().split())
        g[s].append(t)
        g[t].append(s)

    visited = set()
    lowest = [None] * v
    parent = [None] * v
    prenum = [None] * v
    child = defaultdict(list)
    root = 0

    # dfs??§tree?????????
    stack = [(root, None)]
    while stack:
        u, prev = stack.pop()
        if u not in visited:
            parent[u] = prev
            if prev is not None:
                child[prev].append(u)
            visited |= {u}
            prenum[u] = lowest[u] = len(visited)

        stack.extend([(v, u) for v in g[u] if v not in visited])

    # lowest????¨????
    from collections import Counter
    leaf = [i for i in range(v) if not child[i]]
    unfinished = Counter()
    for li in leaf:
        while li is not None:
            candidate = [prenum[li]] + [prenum[i] for i in g[li] if i != parent[li]] + [lowest[i] for i in child[li]]
            lowest[li] = min(candidate)
            li = parent[li]
            if li is not None and 1 < len(child[li]):
                unfinished[li] += 1
                if unfinished[li] < len(child[li]):
                    break

    # ????????????
    bridge = []
    for i in range(v):
        if child[i]:
            for j in child[i]:
                if prenum[i] < lowest[j]:
                    bridge.append((i, j) if i < j else (j, i))
    bridge.sort()
    for bi in bridge:
        print(*bi)

main()