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 collections import defaultdict
import sys
sys.setrecursionlimit(10**7)


def input(): return sys.stdin.readline().rstrip()


# 二つの配列ord,miniを持つ。
V, E = map(int, input().split())
edge = []
graph = [[] for i in range(V)]
for i in range(E):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
    edge.append((min(x, y), max(x, y)))

order = [i for i in range(V)]
mini = [V+1 for i in range(V)]
visited = [False for i in range(V)]

used = defaultdict(bool)
for node in range(V):
    for point in graph[node]:
        used[(node, point)] = False
cnt = 0


def dfs(node):
    global cnt
    visited[node] = True
    cnt += 1
    order[node] = cnt
    mini[node] = cnt
    for point in graph[node]:
        if visited[point] == False:
            used[(node, point)] = True
            dfs(point)
            mini[node] = min(mini[node], mini[point])
        elif not used[(point, node)]:
            mini[node] = min(mini[node], order[point])
    return


dfs(0)

answer = []

for x, y in edge:
    if order[x] < order[y]:
        if order[x] < mini[y]:
            answer.append((x, y))
    elif order[x] > order[y]:
        if order[y] < mini[x]:
            answer.append((x, y))
answer.sort()
for x, y in answer:
    print(x, y)