p02367 Bridges
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
```python
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def low_link(nodes):
    N = len(nodes)
    visited = [False] * N
    prenum = [0] * N
    parent = [0] * N
    lowest = [0] * N
    bridges = []
    timer = 1

    def rec(cur, prev, timer):
        # curを訪問した直後の処理
        prenum[cur] = lowest[cur] = timer
        timer += 1
        visited[cur] = True
        for nxt in nodes[cur]:
            if not visited[nxt]:
                # curからvへ訪問する直前の処理
                parent[nxt] = cur
                timer = rec(nxt, cur, timer)
                # nxtの探索が終了した直後の処理
                lowest[cur] = min(lowest[cur], lowest[nxt])
                # より近い経路を含まないなら橋とする
                if lowest[nxt] == prenum[nxt]:
                    # 番号の小さい方から入れる
                    bridges.append((min(cur, nxt), max(cur, nxt)))
            elif nxt != prev:
                # cur -> nxt がback-edgeの場合の処理
                lowest[cur] = min(lowest[cur], prenum[nxt])
        return timer
    # 必要な各値の取得(非連結に対応するため全頂点から)
    for i in range(N):
        if not visited[i]:
            timer = rec(i, -1, timer)

    # 間接点
    aps = set()
    # ルートの子ノードの数
    np = 0
    for i in range(1, N):
        p = parent[i]
        if p == 0:
            np += 1
        # 条件2の確認
        elif prenum[p] <= lowest[i]:
            aps.add(p)
    # 条件1の確認
    if np > 1:
        aps.add(0)

    return aps, bridges

N, M = MAP()
nodes = [[] for i in range(N)]
for i in range(M):
    u, v = MAP()
    nodes[u].append(v)
    nodes[v].append(u)

aps, bridges = low_link(nodes)

bridges = sorted(bridges)
for x in bridges:
    print(*x)


```