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:
class Graph(): #non-directed
    def __init__(self,n,edge):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.deg = [0 for _ in range(n)]
        for e in edge:
            self.graph[e[0]].append(e[1])
            self.graph[e[1]].append(e[0])
            self.deg[e[0]] += 1
            self.deg[e[1]] += 1

    def lowlink(self): #DFS木, ord, lowを計算
        self.ord = [None for _ in range(self.n)]
        self.low = [None for _ in range(self.n)]
        self.group = [None for _ in range(self.n)]
        self.prev = [None for _ in range(self.n)]
        self.tree = [[] for _ in range(self.n)]
        self.sorted = []
        order = 0
        count = 0
        low = [None for _ in range(self.n)]
        for s in range(self.n):
            if self.group[s] is None:
                stack = [(s, None)]
                while stack:
                    node, par = stack.pop()
                    if self.group[node] is None:
                        self.group[node] = count
                        self.ord[node] = order
                        self.sorted.append(node)
                        order += 1
                        if par is not None:
                            self.prev[node] = par
                            self.tree[par].append(node)
                        for adj in self.graph[node]:
                            if self.group[adj] is None:
                                stack.append((adj, node))
                count += 1
        for node in self.sorted[::-1]:
            self.low[node] = self.ord[node]
            for adj in self.graph[node]:
                if self.prev[adj]  == node:
                    self.low[node] = min(self.low[node], self.low[adj])
                elif self.prev[node] == adj:
                    continue
                else:
                    self.low[node] = min(self.low[node], self.ord[adj])

    def articulation(self):
        res = []
        for node in range(self.n):
            if self.prev[node] is None and len(self.tree[node]) > 1:
                res.append(node)
            if self.prev[node] is not None:
                for adj in self.tree[node]:
                    if self.ord[node] <= self.low[adj]:
                        res.append(node)
                        break
        return res

    def bridge(self):
        res = []
        for node in range(self.n):
            for adj in self.tree[node]:
                if self.ord[node] < self.low[adj]:
                    res.append((node, adj))
        return res


import sys
input = sys.stdin.readline

N, M = map(int, input().split())
E = [tuple(map(int, input().split())) for _ in range(M)]

g = Graph(N, E)
g.lowlink()
res = g.bridge()
res = list(map(lambda x: (min(x), max(x)), res))
res.sort()
if res:
    print('\n'.join(map(lambda x: ' '.join(map(str, x)), res)))