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:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	bridges
# CreatedDate:  2020-07-26 23:07:19 +0900
# LastModified: 2020-07-26 23:42:02 +0900
#


import os
import sys
sys.setrecursionlimit(100000)

# import numpy as np
# import pandas as pd


class Graph():
    def __init__(self, V):
        self.V = V
        self.path = [[] for _ in range(self.V)]
        self.parents = [-1] * self.V
        self.lowlink = [float('inf')] * self.V
        self.order = [float('inf')] * self.V
        self.ap = []

    def add(self, s, t):
        self.path[s].append(t)
        self.path[t].append(s)

    def dfs(self, k, u):
        child = 0
        self.lowlink[u] = k
        self.order[u] = k
        k += 1
        for v in self.path[u]:
            if self.lowlink[v] == float('inf'):
                child += 1
                self.parents[v] = u
                self.dfs(k, v)
                self.lowlink[u] = min(self.lowlink[u], self.lowlink[v])

                if self.lowlink[v] > self.order[u]:
                    self.ap.append(sorted([u, v]))

            elif self.parents[u] != v:
                self.lowlink[u] = min(self.lowlink[u], self.order[v])

    def lowlink_order_print(self):
#        print("lowlink:", self.lowlink)
#        print("order:", self.order)
        self.ap = sorted(self.ap)
        for s in self.ap:
            print("{} {}".format(s[0], s[1]))


def main():
    V, E = map(int, input().split())
    graph = Graph(V)
    for _ in range(E):
        s, t = map(int, input().split())
        graph.add(s, t)
    graph.dfs(0, 0)
    graph.lowlink_order_print()


if __name__ == "__main__":
    main()