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

Source: aizu | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
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):
		prenum[cur] = lowest[cur] = timer
		timer += 1
		visited[cur] = True
		for nxt in nodes[cur]:
			if not visited[nxt]:
				parent[nxt] = cur
				timer = rec(nxt, cur, timer)
				lowest[cur] = min(lowest[cur], lowest[nxt])
				if lowest[nxt] == prenum[nxt]:
					bridges.append((min(cur, nxt), max(cur, nxt)))
			elif nxt != prev:
				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
		elif prenum[p] <= lowest[i]:
			aps.add(p)
	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)


class Edge:
	__slots__ = ('v', 'w')

	def __init__(self, v, w):
		self.v = v
		self.w = w

	def either(self):
		return self.v

	def other(self, v):
		if v == self.v:
			return self.w
		else:
			return self.v

class Graph:

	def __init__(self, v):
		self.v = v
		self._edges = [[] for _ in range(v)]

	def add(self, e):
		self._edges[e.v].append(e)
		self._edges[e.w].append(e)

	def adj(self, v):
		return self._edges[v]

	def edges(self):
		for es in self._edges:
			for e in es:
				yield e

def bridges(graph):

	def visit(v, e):
		nonlocal n
		w = e.other(v)
		if not visited[w]:
			parent[w] = v
			n += 1
			visited[w] = n
			low[w] = n
			return True
		elif w != parent[v]:
			low[v] = min(low[v], visited[w])
			return False

	def leave(p, e):
		c = e.other(p)
		if p == parent[c] and low[c] > visited[p]:
			es.append(e)
		low[p] = min(low[p], low[c])
		return False
	visited = [0] * graph.v
	low = [0] * graph.v
	parent = [-1] * graph.v
	es = []
	s = 0
	n = 1
	visited[s] = n
	low[s] = n
	stack = [(s, e, visit) for e in graph.adj(s)]
	while stack:
		(v, e, func) = stack.pop()
		if func(v, e):
			stack.append((v, e, leave))
			w = e.other(v)
			for ne in graph.adj(w):
				stack.append((w, ne, visit))
	return es

def run():
	(v, e) = [int(i) for i in input().split()]
	g = Graph(v)
	for _ in range(e):
		(s, t) = [int(i) for i in input().split()]
		g.add(Edge(s, t))
	edges = [(e.v, e.w) if e.v < e.w else (e.w, e.v) for e in bridges(g)]
	for (v, w) in sorted(edges):
		print(v, w)
run()


import sys
sys.setrecursionlimit(int(3000000.0))

def generate_adj_table(_v_info):
	for v_detail in _v_info:
		(v_from, v_to) = map(int, v_detail)
		init_adj_table[v_from].append(v_to)
		init_adj_table[v_to].append(v_from)
	return init_adj_table

def graph_dfs(u, visited, parent, low, disc):
	global Time
	children = 0
	visited[u] = True
	disc[u] = Time
	low[u] = Time
	Time += 1
	for v in adj_table[u]:
		if not visited[v]:
			parent[v] = u
			children += 1
			graph_dfs(v, visited, parent, low, disc)
			low[u] = min(low[u], low[v])
			if low[v] > disc[u]:
				ans.append(sorted([u, v]))
		elif v != parent[u]:
			low[u] = min(low[u], disc[v])
	return None

def bridge():
	visited = [False] * vertices
	disc = [float('Inf')] * vertices
	low = [float('Inf')] * vertices
	parent = [-1] * vertices
	for v in range(vertices):
		if not visited[v]:
			graph_dfs(v, visited, parent, low, disc)
	return ans
_input = sys.stdin.readlines()
(vertices, edges) = map(int, _input[0].split())
v_info = map(lambda x: x.split(), _input[1:])
Time = 0
ans = []
init_adj_table = tuple(([] for _ in range(vertices)))
adj_table = generate_adj_table(v_info)
res = bridge()
res.sort()
for ele in res:
	print(*ele)


import sys
from operator import itemgetter
sys.setrecursionlimit(int(3000000.0))

def generate_adj_table(_v_info):
	for v_detail in _v_info:
		(v_from, v_to) = map(int, v_detail)
		init_adj_table[v_from].append(v_to)
		init_adj_table[v_to].append(v_from)
	return init_adj_table

def graph_dfs(u, visited, parent, low, disc):
	global Time
	children = 0
	visited[u] = True
	disc[u] = Time
	low[u] = Time
	Time += 1
	for v in adj_table[u]:
		if not visited[v]:
			parent[v] = u
			children += 1
			graph_dfs(v, visited, parent, low, disc)
			low[u] = min(low[u], low[v])
			if low[v] > disc[u]:
				ans.append(sorted([u, v]))
		elif v != parent[u]:
			low[u] = min(low[u], disc[v])
	return None

def bridge():
	visited = [False] * vertices
	disc = [float('Inf')] * vertices
	low = [float('Inf')] * vertices
	parent = [-1] * vertices
	for v in range(vertices):
		if not visited[v]:
			graph_dfs(v, visited, parent, low, disc)
	return ans
_input = sys.stdin.readlines()
(vertices, edges) = map(int, _input[0].split())
v_info = map(lambda x: x.split(), _input[1:])
Time = 0
ans = []
init_adj_table = tuple(([] for _ in range(vertices)))
adj_table = generate_adj_table(v_info)
res = bridge()
res.sort()
for ele in res:
	print(*ele)


import sys
sys.setrecursionlimit(int(100000.0))

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
_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)


import sys
sys.setrecursionlimit(100000)
(V, E) = list(map(int, input().split()))
Edge = [list(map(int, input().split())) for _ in range(0, E)]
ord = [0 for _ in range(0, V)]
low = [0 for _ in range(0, V)]
used = [False for _ in range(0, V)]
bridge = []
G = [[] for _ in range(0, V)]
for (s, t) in Edge:
	G[s] += [t]
	G[t] += [s]

def dfs(s, p, k):
	global articulation
	used[s] = True
	ord[s] = k
	low[s] = ord[s]
	k += 1
	c = 0
	for t in G[s]:
		if used[t] == False:
			c += 1
			dfs(t, s, k)
			low[s] = min(low[s], low[t])
		elif t != p:
			low[s] = min(low[s], ord[t])
for s in range(0, V):
	if used[s] == False:
		dfs(s, -1, 0)
for (s, t) in Edge:
	if ord[s] < low[t] or ord[t] < low[s]:
		if s < t:
			bridge += [(s, t)]
		else:
			bridge += [(t, s)]
bridge.sort()
for (s, t) in bridge:
	print(s, t)


from math import inf
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 6)

def dfs(v, par):
	global cur
	vis[v] = 1
	disc[v] = cur
	low[v] = cur
	cur += 1
	for i in g[v]:
		if vis[i] == 0:
			dfs(i, v)
			low[v] = min(low[i], low[v])
			if low[i] > disc[v]:
				apts.add((min(v, i), max(v, i)))
		elif i != par:
			low[v] = min(disc[i], low[v])

def articulation_pts():
	global apts, disc, low, vis
	disc = [0] * n
	low = [inf] * n
	vis = [0] * n
	apts = set()
	for i in range(n):
		if vis[i] == 0:
			dfs(i, -1)
(n, e) = map(int, input().split())
cur = 0
g = [[] for i in range(n)]
for i in range(e):
	(x, y) = map(int, input().split())
	g[x].append(y)
	g[y].append(x)
articulation_pts()
apts = sorted(apts)
for i in apts:
	print(*i)


import sys

class LowLinks:

	def __init__(self, edges, v, root=0):
		self.edges = edges
		self.root = root
		self.ord = [None] * v
		self.low = [None] * v
		self.cnt = 0
		self.bridges = []
		self.articulations = set()
		self.par = [None] * v

	def build(self):
		self.search(self.root)

	def search(self, x):
		self.ord[x] = self.cnt
		self.low[x] = self.cnt
		self.cnt += 1
		dim = 0
		for to in self.edges[x]:
			if to == self.par[x]:
				continue
			if self.ord[to] != None:
				self.low[x] = min(self.low[x], self.ord[to])
			else:
				self.par[to] = x
				self.search(to)
				dim += 1
				self.low[x] = min(self.low[x], self.low[to])
				if x != self.root and self.ord[x] <= self.low[to]:
					self.articulations.add(x)
			if x == self.root and dim > 1:
				self.articulations.add(x)
			if self.ord[x] < self.low[to]:
				self.bridges.append((x, to))
sys.setrecursionlimit(1000000)
(v, e) = map(int, input().split())
edges = [[] for _ in range(v)]
for _ in range(e):
	(s, t) = map(int, input().split())
	edges[s].append(t)
	edges[t].append(s)
lowlinks = LowLinks(edges, v)
lowlinks.build()
if lowlinks.bridges:
	bridges = sorted(lowlinks.bridges, key=lambda x: (min(x), max(x)))
	for bridge in bridges:
		print(min(bridge), max(bridge))


import sys
from collections import deque
sys.setrecursionlimit(1000000)

def dfs(current, prev):
	global time
	ord[current] = time
	low[current] = time
	time += 1
	color[current] = BLACK
	for next in G[current]:
		if color[next] == WHITE:
			parent[next] = current
			dfs(next, current)
			low[current] = min(low[current], low[next])
		elif next != prev:
			low[current] = min(low[current], ord[next])

def bridge():
	global time
	time = 1
	dfs(0, -1)
	for (u, v) in edges:
		if ord[u] < low[v] or ord[v] < low[u]:
			br.add((u, v))
G = {}
edges = set([])
br = set([])
(v, n) = map(int, input().split())
for i in range(0, v):
	G[i] = []
for i in range(n):
	(s, t) = map(int, input().split())
	G[s].append(t)
	G[t].append(s)
	edges.add((s, t))
WHITE = 0
BLACK = 2
color = [WHITE] * v
parent = [0] * v
ord = [0] * v
low = [0] * v
parent = [0] * v
bridge()
if br:
	br = list(map(sorted, br))
	br.sort(key=lambda x: x[1])
	br.sort(key=lambda x: x[0])
	for ans in br:
		print(*ans)


mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	input = sys.stdin.readline

	def lowlink(adj, root=1):
		N = len(adj) - 1
		order = [N + 1] * (N + 1)
		low = [N + 1] * (N + 1)
		AP = []
		bridge = []
		st = [root]
		cnt = 1
		par = [0] * (N + 1)
		seq = []
		while st:
			v = st.pop()
			if order[v] != N + 1:
				continue
			order[v] = cnt
			seq.append(v)
			low[v] = cnt
			cnt += 1
			for u in adj[v]:
				if order[u] < cnt:
					if par[v] != u:
						low[v] = min(low[v], order[u])
						continue
				else:
					par[u] = v
					st.append(u)
		child = [[] for _ in range(N + 1)]
		for v in range(1, N + 1):
			child[par[v]].append(v)
		seq.reverse()
		for v in seq:
			for u in child[v]:
				low[v] = min(low[v], low[u])
		for p in range(1, N + 1):
			for c in child[p]:
				if order[p] < low[c]:
					bridge.append((p, c))
		for v in range(1, N + 1):
			if v == root:
				if len(child[v]) > 1:
					AP.append(v)
			else:
				for c in child[v]:
					if order[v] <= low[c]:
						AP.append(v)
						break
		return (AP, bridge)
	(N, M) = map(int, input().split())
	adj = [[] for _ in range(N + 1)]
	for _ in range(M):
		(a, b) = map(int, input().split())
		a += 1
		b += 1
		adj[a].append(b)
		adj[b].append(a)
	(AP, bridge) = lowlink(adj)
	ans = []
	for (u, v) in bridge:
		u -= 1
		v -= 1
		if u > v:
			(u, v) = (v, u)
		ans.append((u, v))
	ans.sort(key=lambda x: x[1])
	ans.sort(key=lambda x: x[0])
	for (u, v) in ans:
		print(u, v)
main()


import sys
sys.setrecursionlimit(200000)
(n, m) = map(int, input().split())
edges = [set() for _ in range(n)]
for _ in range(m):
	(s, t) = map(int, input().split())
	edges[s].add(t)
	edges[t].add(s)
prenum = [None] * n
parent = [None] * n
lowest = [None] * n
counter = 0
bridges = set()

def dfs(cur, prev):
	global counter
	prenum[cur] = lowest[cur] = counter
	counter += 1
	for edge in edges[cur]:
		if prenum[edge] is not None:
			if edge != prev:
				lowest[cur] = min(lowest[cur], prenum[edge])
			continue
		parent[edge] = cur
		dfs(edge, cur)
		lowest[cur] = min(lowest[cur], lowest[edge])
	if prenum[cur] == lowest[cur]:
		bridges.add((cur, prev) if cur < prev else (prev, cur))
dfs(0, -1)
for bridge in sorted(bridges)[1:]:
	print(*bridge)


import sys

class LowLinks:

	def __init__(self, edges, v, root=0):
		self.edges = edges
		self.root = root
		self.ord = [None] * v
		self.low = [None] * v
		self.cnt = 0
		self.bridges = []
		self.articulations = set()
		self.par = [None] * v

	def build(self):
		self.search(self.root)

	def search(self, x):
		self.ord[x] = self.cnt
		self.low[x] = self.cnt
		self.cnt += 1
		dim = 0
		for to in self.edges[x]:
			if to == self.par[x]:
				continue
			if self.ord[to] != None:
				self.low[x] = min(self.low[x], self.ord[to])
			else:
				self.par[to] = x
				self.search(to)
				dim += 1
				self.low[x] = min(self.low[x], self.low[to])
				if x != self.root and self.ord[x] <= self.low[to]:
					self.articulations.add(x)
			if x == self.root and dim > 1:
				self.articulations.add(x)
			if self.ord[x] < self.low[to]:
				self.bridges.append((x, to))
sys.setrecursionlimit(1000000)
(n, m) = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(m):
	(s, t) = map(int, input().split())
	edges[s].append(t)
	edges[t].append(s)
l = LowLinks(edges, n)
l.build()
ans = []
for (i, j) in l.bridges:
	if i > j:
		ans.append((j, i))
	else:
		ans.append((i, j))
ans.sort()
for (i, j) in ans:
	print(i, j)


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)


import sys
sys.setrecursionlimit(10 ** 6)
readline = sys.stdin.readline
write = sys.stdout.write
(N, M) = map(int, readline().split())
G = [[] for i in range(N)]
for i in range(M):
	(u, v) = map(int, readline().split())
	G[u].append(v)
	G[v].append(u)

def construct(G, N):
	P = [0] * N
	G0 = [[] for i in range(N)]
	V = []
	lb = [0] * N

	def dfs(v, p):
		P[v] = p
		V.append(v)
		lb[v] = len(V)
		for w in G[v]:
			if w == p:
				continue
			if lb[w]:
				if lb[v] < lb[w]:
					G0[v].append(w)
				continue
			dfs(w, v)
	dfs(0, -1)
	used = [0] * N
	first = 1
	B = []
	used[0] = 1
	ap = [0] * N
	for u in V:
		if not used[u]:
			p = P[u]
			B.append((u, p) if u < p else (p, u))
			if len(G[u]) > 1:
				ap[u] = 1
			if len(G[p]) > 1:
				ap[p] = 1
		cycle = 0
		for v in G0[u]:
			w = v
			while w != u and (not used[w]):
				used[w] = 1
				w = P[w]
			if w == u:
				cycle = 1
		if cycle:
			if not first:
				ap[u] = 1
			first = 0
	A = [v for v in range(N) if ap[v]]
	return (B, A)
(B, A) = construct(G, N)
B.sort()
for (u, v) in B:
	write('%d %d\n' % (u, v))


import sys
sys.setrecursionlimit(100000)

def dfs(v, tm):
	dts[v] = est[v] = tm + 1
	child = 0
	for i in adj[v]:
		if est[i] == float('inf'):
			child += 1
			parents[i] = v
			dfs(i, tm + 1)
			est[v] = min(est[v], est[i])
			if est[i] > dts[v]:
				bridges.append((v, i)) if v < i else bridges.append((i, v))
		elif parents[v] != i:
			est[v] = min(est[v], dts[i])
(nv, ne) = map(int, input().split(' '))
adj = [[] for _ in range(nv)]
est = [float('inf')] * nv
parents = [None] * nv
dts = [0] * nv
bridges = []
for _ in range(ne):
	(s, t) = map(int, input().split(' '))
	adj[s].append(t)
	adj[t].append(s)
dfs(0, 0)
bridges.sort(key=lambda tup: (tup[0], tup[1]))
[print(str(bridge[0]) + ' ' + str(bridge[1])) for bridge in bridges]


import os
import sys
sys.setrecursionlimit(100000)

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):
		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()
main()


import sys
f_i = sys.stdin
(V, E) = map(int, f_i.readline().split())
adj = [[] for i in range(V)]
for l_i in f_i:
	(s, t) = map(int, l_i.split())
	adj[s].append(t)
	adj[t].append(s)
prenum = [1] + [None] * (V - 1)
parent = [0] * V
lowest = [1] + [V] * (V - 1)
import collections
path = collections.deque()
path.append(0)
cnt = 1
while path:
	u = path[-1]
	adj_v = adj[u]
	for v in adj_v:
		if not prenum[v]:
			parent[v] = u
			path.append(v)
			cnt += 1
			prenum[v] = cnt
			lowest[v] = cnt
			adj[u].remove(v)
			adj[v].remove(u)
			break
	if u == path[-1]:
		for v in adj_v:
			lowest[u] = min(lowest[u], lowest[v])
			adj[u].remove(v)
			adj[v].remove(u)
		p = parent[u]
		lowest[p] = min(lowest[u], lowest[p])
		path.pop()
bridge = []
for u in range(1, V):
	p = parent[u]
	if prenum[p] < lowest[u]:
		b = [p, u]
		b.sort()
		bridge.append(b)
bridge.sort()
for b in bridge:
	print(*b)


import sys
sys.setrecursionlimit(int(100000.0))

def generate_adj_table(_v_info):
	for v_detail in _v_info:
		(v_from, v_to) = map(int, v_detail)
		init_adj_table[v_from].append(v_to)
		init_adj_table[v_to].append(v_from)
	return init_adj_table

def graph_dfs(u, visited, parent, low, disc):
	global Time
	children = 0
	visited[u] = True
	disc[u] = Time
	low[u] = Time
	Time += 1
	for v in adj_table[u]:
		if not visited[v]:
			parent[v] = u
			children += 1
			graph_dfs(v, visited, parent, low, disc)
			low[u] = min(low[u], low[v])
			if low[v] > disc[u]:
				ans.append(sorted([u, v]))
		elif v != parent[u]:
			low[u] = min(low[u], disc[v])
	return None

def bridge():
	visited = [False] * vertices
	disc = [float('Inf')] * vertices
	low = [float('Inf')] * vertices
	parent = [-1] * vertices
	for v in range(vertices):
		if not visited[v]:
			graph_dfs(v, visited, parent, low, disc)
	return ans
_input = sys.stdin.readlines()
(vertices, edges) = map(int, _input[0].split())
v_info = map(lambda x: x.split(), _input[1:])
Time = 0
ans = []
init_adj_table = tuple(([] for _ in range(vertices)))
adj_table = generate_adj_table(v_info)
res = bridge()
res.sort()
for ele in res:
	print(*ele)


import sys
sys.setrecursionlimit(int(100000.0))

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
_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()
for ele in sorted(ans):
	print(*ele)


import sys
sys.setrecursionlimit(10 ** 9)

def input():
	return sys.stdin.readline().strip()

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST():
	return list(map(int, input().split()))
INF = float('inf')
(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)
visited = [False] * N
timer = 1
prenum = [0] * (N + 1)
lowest = [0] * (N + 1)
ans = []

def rec(cur, prev):
	global timer
	prenum[cur] = lowest[cur] = timer
	timer += 1
	visited[cur] = True
	for nxt in nodes[cur]:
		if not visited[nxt]:
			rec(nxt, cur)
			lowest[cur] = min(lowest[cur], lowest[nxt])
			if lowest[nxt] == prenum[nxt]:
				ans.append((min(cur, nxt), max(cur, nxt)))
		elif nxt != prev:
			lowest[cur] = min(lowest[cur], lowest[nxt])
rec(0, -1)
ans.sort()
for edge in ans:
	print(*edge)


import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

class LowLinks:

	def __init__(self, edges, edges_num: int):
		self.edges = edges
		self.V = len(edges)
		self.order = [-1] * V
		self.low = [float('inf')] * V
		self.bridges = []
		self.articulations = []
		if len(edges[0]) > 1 and edges_num == self.V - 1:
			self.articulations.append(0)
		self.k = 0

	def build(self):
		self.dfs(0, 0)

	def get_bridges(self) -> tuple:
		return self.bridges

	def get_articulations(self) -> tuple:
		return self.articulations

	def dfs(self, v: int, prev: int):
		self.order[v] = self.k
		self.low[v] = self.k
		self.k += 1
		is_articulation = False
		for to in self.edges[v]:
			if self.order[to] < 0:
				self.dfs(to, v)
				self.low[v] = min(self.low[v], self.low[to])
				if self.order[v] < self.low[to]:
					self.bridges.append((v, to) if v < to else (to, v))
				is_articulation |= self.order[v] <= self.low[to]
			elif to != prev:
				self.low[v] = min(self.low[v], self.order[to])
		if v > 0 and is_articulation:
			self.articulations.append(v)
(V, E) = map(int, readline().split())
edges = [[] for _ in range(V)]
for _ in range(E):
	(s, t) = map(int, readline().split())
	edges[s].append(t)
	edges[t].append(s)
lowlinks = LowLinks(edges, E)
lowlinks.build()
bridges = lowlinks.get_bridges()
bridges.sort()
if bridges:
	for (s, t) in bridges:
		print(s, t)


def solve():
	(N, M) = map(int, input().split())
	edges = [[] for _ in [0] * N]
	for _ in [0] * M:
		(a, b) = map(int, input().split())
		edges[a].append(b)
		edges[b].append(a)
	bridges = sorted(((a, b) if a < b else (b, a) for (a, b) in get_lowlink(edges, M)[0]))
	for (a, b) in bridges:
		print(a, b)

def get_lowlink(edges, edge_num):
	import sys
	sys.setrecursionlimit(10 ** 7)
	n = len(edges)
	order = [-1] * n
	low = [float('inf')] * n
	bridges = []
	articulations = [0] if edge_num == n - 1 and len(edges[0]) > 1 else []
	(append_bridge, append_articulation) = (bridges.append, articulations.append)

	def dfs(v, prev, k):
		order[v] = low[v] = k
		is_articulation = False
		for dest in edges[v]:
			if order[dest] == -1:
				dfs(dest, v, k + 1)
				if low[v] > low[dest]:
					low[v] = low[dest]
				if order[v] < low[dest]:
					append_bridge((v, dest))
				is_articulation |= order[v] <= low[dest]
			elif dest != prev and low[v] > order[dest]:
				low[v] = order[dest]
		if v > 0 and is_articulation:
			append_articulation(v)
	dfs(0, 0, 0)
	return (bridges, articulations)
solve()


import sys
sys.setrecursionlimit(200000)
(v, e) = map(int, input().split())
edges = [set() for _ in range(v)]
for _ in range(e):
	(s, t) = map(int, input().split())
	edges[s].add(t)
	edges[t].add(s)
prenum = [None] * v
parent = [None] * v
lowest = [None] * v
counter = 0
bridges = set()

def dfs(cur, prev):
	global counter
	prenum[cur] = lowest[cur] = counter
	counter += 1
	for edge in edges[cur]:
		if prenum[edge] is not None:
			if edge != prev:
				lowest[cur] = min(lowest[cur], prenum[edge])
			continue
		parent[edge] = cur
		dfs(edge, cur)
		lowest[cur] = min(lowest[cur], lowest[edge])
	if prenum[cur] == lowest[cur]:
		bridges.add((cur, prev) if cur < prev else (prev, cur))
dfs(0, -1)
for bridge in sorted(bridges)[1:]:
	print(*bridge)


import sys
sys.setrecursionlimit(10 ** 6)
(V, E) = list(map(int, input().split()))
G = [[] for i in range(V)]
for i in range(E):
	(s, t) = list(map(int, input().split()))
	G[s].append(t)
	G[t].append(s)

class LowLink:

	def main(G, V):
		LowLink.G = G
		LowLink.used = [False] * V
		LowLink.ord = [0] * V
		LowLink.low = [0] * V
		LowLink.aps = []
		LowLink.bridges = []
		n = 0
		for i in range(V):
			if not LowLink.used[i]:
				n = LowLink.dfs(i, n, -1)
		LowLink.aps.sort()
		LowLink.bridges.sort()

	def dfs(v, n, par):
		LowLink.used[v] = True
		LowLink.ord[v] = n + 1
		n += 1
		LowLink.low[v] = LowLink.ord[v]
		is_aps = False
		chi = 0
		for u in LowLink.G[v]:
			if not LowLink.used[u]:
				chi += 1
				n = LowLink.dfs(u, n, v)
				LowLink.low[v] = min(LowLink.low[v], LowLink.low[u])
				if par != -1 and LowLink.ord[v] <= LowLink.low[u]:
					is_aps = True
				if LowLink.ord[v] < LowLink.low[u]:
					LowLink.bridges.append((min(v, u), max(v, u)))
			elif u != par:
				LowLink.low[v] = min(LowLink.low[v], LowLink.ord[u])
		if par == -1 and chi >= 2:
			is_aps = True
		if is_aps:
			LowLink.aps.append(v)
		return n
LowLink.main(G, V)
for v in LowLink.bridges:
	print(*v)


from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def I():
	return int(sys.stdin.readline())

def LS():
	return [list(x) for x in sys.stdin.readline().split()]

def S():
	res = list(sys.stdin.readline())
	if res[-1] == '\n':
		return res[:-1]
	return res

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]
sys.setrecursionlimit(1000000)
mod = 1000000007

class LowLink:

	def __init__(self, v):
		self.size = len(v)
		self.v = v
		self.pre = [None] * self.size
		self.low = [None] * self.size
		self.articulation = []
		self.bridge = []
		for x in range(self.size):
			if self.pre[x] is None:
				self.cnt = 0
				self.dfs(x, None)

	def dfs(self, x, par):
		self.pre[x] = self.low[x] = self.cnt
		self.cnt += 1
		is_articulation = False
		n = 0
		for y in self.v[x]:
			if self.pre[y] is None:
				n += 1
				lowy = self.dfs(y, x)
				if lowy < self.low[x]:
					self.low[x] = lowy
				if self.pre[x] <= lowy:
					if self.pre[x]:
						is_articulation = True
					if self.pre[x] < lowy:
						self.bridge.append((x, y))
			elif par != y and self.pre[y] < self.low[x]:
				self.low[x] = self.pre[y]
		if par is None and n > 1:
			is_articulation = True
		if is_articulation:
			self.articulation.append(x)
		return self.low[x]

def solve():
	(n, m) = LI()
	v = [[] for i in range(n)]
	for i in range(m):
		(a, b) = LI()
		v[a].append(b)
		v[b].append(a)
	lowlink = LowLink(v)
	bridge = lowlink.bridge
	for i in range(len(bridge)):
		(l, r) = bridge[i]
		if r < l:
			bridge[i] = (r, l)
	for i in sorted(bridge):
		print(*i)
	return
solve()


from sys import stdin
readline = stdin.readline

def main():
	(v, e) = map(int, readline().split())
	from collections import defaultdict
	g = defaultdict(list)
	for _ in range(e):
		(s, t) = map(int, readline().split())
		g[s].append(t)
		g[t].append(s)
	visited = set()
	lowest = [None] * v
	parent = [None] * v
	prenum = [None] * v
	child = defaultdict(list)
	root = 0
	stack = [(root, None)]
	while stack:
		(u, prev) = stack.pop()
		if u not in visited:
			parent[u] = prev
			if prev is not None:
				child[prev].append(u)
			visited |= {u}
			prenum[u] = lowest[u] = len(visited)
		stack.extend([(v, u) for v in g[u] if v not in visited])
	from collections import Counter
	leaf = [i for i in range(v) if not child[i]]
	unfinished = Counter()
	for li in leaf:
		while li is not None:
			candidate = [prenum[li]] + [prenum[i] for i in g[li] if i != parent[li]] + [lowest[i] for i in child[li]]
			lowest[li] = min(candidate)
			li = parent[li]
			if li is not None and 1 < len(child[li]):
				unfinished[li] += 1
				if unfinished[li] < len(child[li]):
					break
	bridge = []
	for i in range(v):
		if child[i]:
			for j in child[i]:
				if prenum[i] < lowest[j]:
					bridge.append((i, j) if i < j else (j, i))
	bridge.sort()
	for bi in bridge:
		print(*bi)
main()


import sys
sys.setrecursionlimit(10 ** 8)

def lowLink(N: int, Adj: list):
	articulation = []
	bridge = []
	order = [None] * N
	lowest = [1 << 100] * N

	def _dfs(cur, pre, k):
		order[cur] = lowest[cur] = k
		is_articulation = False
		cnt = 0
		for nxt in Adj[cur]:
			if order[nxt] is None:
				cnt += 1
				_dfs(nxt, cur, k + 1)
				if lowest[cur] > lowest[nxt]:
					lowest[cur] = lowest[nxt]
				is_articulation |= pre >= 0 and lowest[nxt] >= order[cur]
				if order[cur] < lowest[nxt]:
					if cur < nxt:
						bridge.append((cur, nxt))
					else:
						bridge.append((nxt, cur))
			elif nxt != pre and lowest[cur] > order[nxt]:
				lowest[cur] = order[nxt]
		is_articulation |= pre < 0 and cnt > 1
		if is_articulation:
			articulation.append(cur)
	_dfs(0, -1, 0)
	return (articulation, bridge)

def main():
	(n, m, *L) = map(int, open(0).read().split())
	adj = [[] for _ in range(n)]
	for (s, t) in zip(*[iter(L)] * 2):
		adj[s] += (t,)
		adj[t] += (s,)
	(_, bridge) = lowLink(n, adj)
	for (x, y) in sorted(bridge):
		print(x, y)
main()


from collections import defaultdict
import sys
sys.setrecursionlimit(100000)

def seq():
	a = 1
	while True:
		yield a
		a += 1

def dfs(here, went, connect, discovery, low, answer, seq):
	went |= {here}
	discovery[here] = low[here] = next(seq)
	child = 0
	for con in connect[here]:
		if con not in went:
			parent[con] = here
			child += 1
			dfs(con, went, connect, discovery, low, answer, seq)
			low[here] = min(low[here], low[con])
			if discovery[here] < low[con]:
				answer[min(here, con)].append(max(here, con))
		elif parent[here] != con:
			low[here] = min(low[here], discovery[con])
(vertices, edges) = (int(n) for n in input().split(' '))
connect = defaultdict(list)
for _ in range(edges):
	(v1, v2) = (int(n) for n in input().split(' '))
	connect[v1].append(v2)
	connect[v2].append(v1)
answer = defaultdict(list)
new_seq = seq()
went = set()
discovery = [0 for n in range(vertices)]
low = [float('inf') for n in range(vertices)]
parent = [None for n in range(vertices)]
dfs(0, went, connect, discovery, low, answer, new_seq)
for k in sorted(answer.keys()):
	for n in sorted(answer[k]):
		print(k, n)


import sys
sys.setrecursionlimit(int(1000000.0))
(n, m) = map(int, input().split())
edges = {}
for i in range(m):
	(s, t) = map(int, input().split())
	if s not in edges:
		edges[s] = set()
	if t not in edges:
		edges[t] = set()
	edges[s].add(t)
	edges[t].add(s)
order = [0] * n
lowlink = [0] * n
visited = set()
bridges = set()

def dfs(v, p, i):
	visited.add(v)
	i += 1
	lowlink[v] = order[v] = i
	if v not in edges:
		return
	for t in edges[v]:
		if t not in visited:
			dfs(t, v, i)
			lowlink[v] = min(lowlink[v], lowlink[t])
			if lowlink[t] == order[t]:
				bridges.add((min(v, t), max(v, t)))
		elif t != p:
			lowlink[v] = min(lowlink[v], lowlink[t])
k = 0
for i in range(n):
	if i not in visited:
		dfs(i, -1, k)
for (s, t) in sorted(bridges):
	print(s, t)


import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

class LowLink:

	def __init__(self, G):
		self.N = len(G)
		self.G = G
		self.low = [-1] * self.N
		self.ord = [-1] * self.N

	def _dfs(self, v, time, p=-1):
		self.ord[v] = self.low[v] = time
		time += 1
		isArticulation = False
		cnt = 0
		for e in self.G[v]:
			if self.low[e] < 0:
				cnt += 1
				self._dfs(e, time, v)
				self.low[v] = min(self.low[v], self.low[e])
				if p != -1 and self.ord[v] <= self.low[e]:
					isArticulation = True
				if self.ord[v] < self.low[e]:
					if v < e:
						self.bridge.append((v, e))
					else:
						self.bridge.append((e, v))
			elif e != p:
				self.low[v] = min(self.low[v], self.ord[e])
		if p == -1 and cnt >= 2:
			isArticulation = True
		if isArticulation:
			self.articulation.append(v)

	def build(self):
		self.articulation = []
		self.bridge = []
		self._dfs(0, 0)

def main():
	(V, E) = map(int, input().split())
	G = [[] for _ in range(V)]
	for _ in range(E):
		(a, b) = map(int, input().split())
		G[a].append(b)
		G[b].append(a)
	lowlink = LowLink(G)
	lowlink.build()
	ans = lowlink.bridge
	ans.sort()
	if ans:
		for t in ans:
			print(*t)
main()


import sys
sys.setrecursionlimit(10 ** 9)

def input():
	return sys.stdin.readline().strip()

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST():
	return list(map(int, input().split()))
INF = float('inf')
(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)
timer = 1
prenum = [0] * (N + 1)
lowest = [0] * (N + 1)
ans = []

def rec(cur, prev):
	global timer
	prenum[cur] = lowest[cur] = timer
	timer += 1
	for nxt in nodes[cur]:
		if not prenum[nxt]:
			rec(nxt, cur)
			lowest[cur] = min(lowest[cur], lowest[nxt])
			if lowest[nxt] == prenum[nxt]:
				ans.append((min(cur, nxt), max(cur, nxt)))
		elif nxt != prev:
			lowest[cur] = min(lowest[cur], lowest[nxt])
rec(0, -1)
ans.sort()
for edge in ans:
	print(*edge)


import sys, collections
sys.setrecursionlimit(100000)
INF = float('inf')
(V, E) = map(int, sys.stdin.readline().split())
st = tuple((tuple(map(int, sys.stdin.readline().rstrip().split())) for _ in range(E)))
G = [[] for _ in range(V)]
for (s, t) in st:
	G[s].append(t)
	G[t].append(s)
visited = set()
prenum = [0] * V
parent = [0] * V
lowest = [0] * V
timer = 0

def dfs(current, prev):
	global timer
	parent[current] = prev
	prenum[current] = lowest[current] = timer
	timer += 1
	visited.add(current)
	for nex in G[current]:
		if not nex in visited:
			dfs(nex, current)
			lowest[current] = min(lowest[current], lowest[nex])
		elif nex != prev:
			lowest[current] = min(lowest[current], prenum[nex])
dfs(0, -1)
ret = []
for i in range(1, V):
	p = parent[i]
	if prenum[p] < lowest[i]:
		if p < i:
			ret.append([p, i])
		else:
			ret.append([i, p])
ret = sorted(list(ret))
for (s, t) in ret:
	print(s, t)


from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 7)

def input():
	return sys.stdin.readline().rstrip()
(V, E) = map(int, input().split())
edge = []
graph = [[] for i in range(V)]
for i in range(E):
	(x, y) = map(int, input().split())
	graph[x].append(y)
	graph[y].append(x)
	edge.append((min(x, y), max(x, y)))
order = [i for i in range(V)]
mini = [V + 1 for i in range(V)]
visited = [False for i in range(V)]
used = defaultdict(bool)
for node in range(V):
	for point in graph[node]:
		used[node, point] = False
cnt = 0

def dfs(node):
	global cnt
	visited[node] = True
	cnt += 1
	order[node] = cnt
	mini[node] = cnt
	for point in graph[node]:
		if visited[point] == False:
			used[node, point] = True
			dfs(point)
			mini[node] = min(mini[node], mini[point])
		elif not used[point, node]:
			mini[node] = min(mini[node], order[point])
	return
dfs(0)
answer = []
for (x, y) in edge:
	if order[x] < order[y]:
		if order[x] < mini[y]:
			answer.append((x, y))
	elif order[x] > order[y]:
		if order[y] < mini[x]:
			answer.append((x, y))
answer.sort()
for (x, y) in answer:
	print(x, y)


import sys
from typing import List, Set
sys.setrecursionlimit(200000)

def dfs(cur: int, prev: int) -> None:
	global prenum, parent, lowest, counter, bridges
	prenum[cur] = lowest[cur] = counter
	counter += 1
	for edge in edges[cur]:
		if prenum[edge] != sys.maxsize:
			if edge != prev:
				lowest[cur] = min(lowest[cur], prenum[edge])
			continue
		parent[edge] = cur
		dfs(edge, cur)
		lowest[cur] = min(lowest[cur], lowest[edge])
	if prenum[cur] == lowest[cur]:
		bridges.add((cur, prev) if cur < prev else (prev, cur))
(V, E) = map(int, input().split())
edges: List[Set[int]] = [set() for _ in range(V)]
for _ in range(E):
	(s, t) = map(int, input().split())
	edges[s].add(t)
	edges[t].add(s)
prenum = [sys.maxsize] * V
parent = [sys.maxsize] * V
lowest = [sys.maxsize] * V
counter = 0
bridges = set()
dfs(0, -1)
for bridge in sorted(bridges)[1:]:
	print(*bridge)


def bridges(E, s):
	N = len(E)
	preorder = [-1] * N
	lowpt = [N] * N
	bridge = []
	stack = [(s, -1, 0)]
	pre_num = 0
	while stack:
		(v, p, st) = stack.pop()
		if st == 0 and preorder[v] < 0:
			preorder[v] = pre_num
			lowpt[v] = pre_num
			pre_num += 1
			n_children = 0
			for u in E[v]:
				if preorder[u] >= 0:
					if u != p:
						lowpt[v] = min(lowpt[v], preorder[u])
					continue
				if n_children == 0:
					stack += [(v, p, 2), (u, v, 0)]
					n_children += 1
				else:
					stack += [(v, p, 1), (u, v, 0)]
					n_children += 1
			if n_children == 0:
				lowpt[p] = min(lowpt[p], lowpt[v])
				if lowpt[v] > preorder[p]:
					bridge.append((v, p) if v < p else (p, v))
		elif st == 0 and preorder[v] >= 0:
			continue
		elif st == 1:
			continue
		elif p != -1:
			lowpt[p] = min(lowpt[p], lowpt[v])
			if lowpt[v] > preorder[p]:
				bridge.append((v, p) if v < p else (p, v))
	return bridge
(N, M) = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
	(s, t) = map(int, input().split())
	E[s].append(t)
	E[t].append(s)
br = sorted(bridges(E, 0))
for (s, t) in br:
	print(s, t)


class Graph:

	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):
		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)))