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:
def bridges(E, s):
    N = len(E)
    preorder = [-1] * N # a dfs preordering of each vertex
    lowpt = [N] * N # for finding a cut-vertex
    bridge = []
    stack = [(s, -1, 0)] # (vertex, parent, status)
    pre_num = 0 # current preordering
    while stack:
        v, p, st = stack.pop()
        if st == 0 and preorder[v] < 0: # visited v for the first time
            preorder[v] = pre_num
            lowpt[v] = pre_num
            pre_num += 1
            n_children = 0
            for u in E[v]:
                if preorder[u] >= 0:
                    if u != p: # the edge (v, u) is a back edge, which is not in dfs search tree
                        lowpt[v] = min(lowpt[v], preorder[u])
                    continue
                if n_children == 0:
                    stack += [(v, p, 2), (u, v, 0)]
                    n_children += 1
                else:
                    stack += [(v, p, 1), (u, v, 0)]
                    n_children += 1
            if n_children == 0: # v is a leaf of the dfs search tree
                lowpt[p] = min(lowpt[p], lowpt[v])
                if lowpt[v] > preorder[p]: bridge.append((v, p) if v < p else (p, v))
        elif st == 0 and preorder[v] >= 0: # the edge (v, p) is a back edge
            continue
        elif st == 1: # now searching
            continue
        else: # search finished
            if p != -1:
                lowpt[p] = min(lowpt[p], lowpt[v])
                if lowpt[v] > preorder[p]: bridge.append((v, p) if v < p else (p, v))
    return bridge

N, M = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
    s, t = map(int, input().split())
    E[s].append(t); E[t].append(s)
br = sorted(bridges(E, 0))
for s, t in br:
    print(s, t)