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 typing import List
from typing import Tuple
from functools import cmp_to_key
import sys

sys.setrecursionlimit(100000)

def find_bridges(adj, n) -> List[Tuple[int, int]]:
    mark = [False for _ in range(n)] 
    edges = []
    low_link = [None for _ in range(n)]
    id = [0]

    for v in range(n):
        if not mark[v]:
            ____find_bridges(v, -1, adj, id, low_link, mark, edges)
    return edges


def ____find_bridges(node: int, parent: int, adj, id: List[int], low_link: List[int], mark: List[bool], edges):

    mark[node] = True
    low_link[node] = id[0]
    node_id = id[0]

    for v in adj[node]:
        if v == parent: continue
        if not mark[v]:
            id[0] += 1
            ____find_bridges(v, node, adj, id, low_link, mark, edges)
        low_link[node] = min(low_link[node], low_link[v])
        if low_link[v] > node_id:
            edges.append([node, v])

def read() -> Tuple[List, int]:

    info = [int(e) for e in input().split()]
    n, e = info[0], info[1]
    adj = [[] for _ in range(n)]
    for _ in range(e):
        edge = [int(i) for i in input().split()]
        adj[edge[0]].append(edge[1])
        adj[edge[1]].append(edge[0])
    
    return adj, n

def custom_cmp(edgeA, edgeB):
    if edgeA[0] == edgeB[0]:
        return edgeA[1] - edgeB[1]
    
    return edgeA[0] - edgeB[0]

def process_output(edges: List[List[int]]) -> List[List[int]]:
    for edge in edges:
        edge.sort()
    n_edges = list(sorted(edges, key=cmp_to_key(custom_cmp)))
    return n_edges

def show(edges):
    for edge in edges:
        print('%d %d' % (edge[0], edge[1]))

adj, n = read()
edges = find_bridges(adj, n)
n_edges = process_output(edges)
show(n_edges)