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 -*-

"""
input:
5 4
0 1
1 2
2 3
3 4

output:
0 1
1 2
2 3
3 4
"""

import sys

sys.setrecursionlimit(int(1e5))


def dfs_Tarjan(current, visited, parent, low, disc):
    global timer
    children = 0
    visited[current] = True
    disc[current] = timer
    low[current] = timer
    timer += 1

    for adj in adj_table[current]:
        if not visited[adj]:
            parent[adj] = current
            children += 1
            dfs_Tarjan(adj, visited, parent, low, disc)
            low[current] = min(low[current], low[adj])
            if low[adj] > disc[current]:
                ans.append(sorted([current, adj]))
        elif adj != parent[current]:
            low[current] = min(low[current], disc[adj])

    return None


def dfs_init():
    visited = [False] * v_num
    disc = [float("Inf")] * v_num
    low = [float("Inf")] * v_num
    parent = [-1] * v_num

    for v in range(v_num):
        if not visited[v]:
            dfs_Tarjan(v, visited, parent, low, disc)

    return ans


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    v_num, e_num = map(int, _input[0].split())
    edges = map(lambda x: x.split(), _input[1:])
    adj_table = tuple([] for _ in range(v_num))
    for v_info in edges:
        source, target = map(int, v_info)
        adj_table[source].append(target)
        adj_table[target].append(source)
        
    timer = 0
    ans = list()

    dfs_init()
    ans.sort()
    for ele in ans:
        print(*ele)