Given an undirected Connected graph of V vertices and E edges.
A critical connection is an edge that, if removed, will make some nodes unable to reach some other nodes. Find all critical connections in the graph.
Note: There are many possible orders for the answer. You are supposed to print the edges in sorted order, and also an edge should be in sorted order too. So if there's an edge between node 1 and 2, you should print it like (1,2) and not (2,1).
Example 1:
Input:
Output:
0 1
0 2
Explanation: 
Both the edges in the graph are Crtical
connections.
Example 2:
Input:
Output:
2 3
Explanation:
The edge between nodes 2 and 3 is the only
Critical connection in the given graph.
Your task:
You dont need to read input or print anything. Your task is to complete the function criticalConnections() which takes the integer V denoting the number of vertices and an adjacency list adj as input parameters and returns  a list of lists containing the Critical connections in the sorted order.
Expected Time Complexity: O(V + E)
Expected Auxiliary Space: O(V)
Constraints:
1 ≤ V, E ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

    def criticalConnections(self, V, adj):

        # code here

Solutions:
class Solution:

	def dfs(self, sv, parent, low, tin, bridges, vis, timer):
		vis.add(sv)
		tin[sv] = low[sv] = timer
		timer += 1
		for nbr in adj[sv]:
			if nbr == parent:
				continue
			if nbr not in vis:
				self.dfs(nbr, sv, low, tin, bridges, vis, timer)
				low[sv] = min(low[nbr], low[sv])
				if tin[sv] < low[nbr]:
					bridges.append([sv, nbr])
			else:
				low[sv] = min(low[nbr], low[sv])
		return

	def criticalConnections(self, V, adj):
		tin = [0 for i in range(V)]
		low = [0 for i in range(V)]
		bridges = []
		vis = set()
		timer = 1
		for i in range(V):
			if i not in vis:
				self.dfs(i, -1, low, tin, bridges, vis, timer)
		for ele in bridges:
			ele.sort()
		bridges.sort()
		return bridges


class Solution:

	def criticalConnections(self, V, adj):
		return bridges_finder(adj)
from math import inf

def bridges_finder(G):

	def dfs_visit(G, u, bridges):
		nonlocal time
		visited[u] = True
		time += 1
		t[u] = time
		low[u] = time
		for v in G[u]:
			if not visited[v]:
				parent[v] = u
				dfs_visit(G, v, bridges)
				low[u] = min(low[u], low[v])
				if low[v] > t[u]:
					bridges.append(sorted([u, v]))
			elif v != parent[u]:
				low[u] = min(low[u], t[v])
	n = len(G)
	visited = [False] * n
	parent = [None] * n
	t = [float(inf)] * n
	low = [float(inf)] * n
	bridges = []
	time = 0
	for u in range(n):
		if not visited[u]:
			dfs_visit(G, u, bridges)
	return sorted(bridges)


class Solution:
	timer = 1

	def criticalConnections(self, V, adj):

		def dfs(node, parent, v, desc, low, adj, bridges):
			v.add(node)
			low[node] = desc[node] = Solution.timer
			Solution.timer += 1
			for nbr in adj[node]:
				if nbr == parent:
					continue
				if nbr not in v:
					dfs(nbr, node, v, desc, low, adj, bridges)
					low[node] = min(low[node], low[nbr])
					if low[nbr] > desc[node]:
						if node < nbr:
							bridges.append([node, nbr])
						else:
							bridges.append([nbr, node])
				else:
					low[node] = min(low[node], low[nbr])
		bridges = []
		v = set()
		desc = [0] * V
		low = [0] * V
		dfs(0, -1, v, desc, low, adj, bridges)
		bridges.sort()
		return bridges


class Solution:

	def criticalConnections(self, v, adj):
		ans = []
		dis = [-1 for _ in range(v)]
		low = [-1 for _ in range(v)]
		visited = [False for _ in range(v)]
		timer = [0]

		def dfs(node, parent, timer):
			visited[node] = True
			dis[node] = timer[0]
			low[node] = timer[0]
			timer[0] += 1
			for ngh in adj[node]:
				if ngh == parent:
					continue
				if visited[ngh] == False:
					dfs(ngh, node, timer)
					low[node] = min(low[node], low[ngh])
					if dis[node] < low[ngh]:
						if node > ngh:
							ans.append(tuple([ngh, node]))
						else:
							ans.append(tuple([node, ngh]))
				else:
					low[node] = min(low[node], dis[ngh])
		for i in range(v):
			if visited[i] == False:
				dfs(i, -1, timer)
		ans = list(set(ans))
		ans.sort()
		return ans


class Solution:

	def criticalConnections(self, V, adj):

		def Articulation_Point(u):
			low[u] = time[0]
			disc[u] = time[0]
			time[0] += 1
			visited[u] = True
			for v in adj[u]:
				if visited[v] == False:
					parent[v] = u
					Articulation_Point(v)
					low[u] = min(low[u], low[v])
					if low[v] > disc[u]:
						ans.append(sorted([u, v]))
				elif parent[u] != v:
					low[u] = min(low[u], disc[v])
		ans = []
		low = [sys.maxsize for i in range(V)]
		disc = [sys.maxsize for i in range(V)]
		parent = [-1 for i in range(V)]
		time = [0]
		visited = [False for i in range(V)]
		for i in range(V):
			if visited[i] == False:
				Articulation_Point(i)
		return sorted(ans)


class Solution:

	def criticalConnections(self, V, adj):
		(vis, t1, t2, par, bridges, time) = (set(), [0 for i in range(V)], [0 for i in range(V)], {}, [], 1)
		par[0] = -1
		vis.add(0)
		t1[0] = t2[0] = time

		def dfs(i, vis, t1, t2, par, bridges, time):
			for j in adj[i]:
				if j not in vis:
					time += 1
					t1[j] = t2[j] = time
					par[j] = i
					vis.add(j)
					dfs(j, vis, t1, t2, par, bridges, time)
					t2[i] = min(t2[i], t2[j])
					if t1[i] < t2[j]:
						if i > j:
							bridges.append([j, i])
						else:
							bridges.append([i, j])
				elif par[i] != j:
					t2[i] = min(t2[j], t2[i])
		dfs(0, vis, t1, t2, par, bridges, time)
		return sorted(bridges)


class Solution:

	def dfs(self, node, parent, t, lt, v, c):
		t[node] = lt[node] = self.timer
		self.timer += 1
		v[node] = 1
		for i in c[node]:
			if i == parent:
				continue
			elif v[i] == 0:
				self.dfs(i, node, t, lt, v, c)
				lt[node] = min(lt[node], lt[i])
				if lt[i] > t[node]:
					self.bridges.append([min(node, i), max(node, i)])
			else:
				lt[node] = min(lt[i], lt[node])

	def criticalConnections(self, n, adj):
		lt = [0] * n
		t = [0] * n
		v = [0] * n
		self.timer = 1
		self.bridges = []
		self.dfs(0, -1, t, lt, v, adj)
		return sorted(self.bridges)


import sys

class Solution:

	def dfs(self, V, adj, visited, parents, disc, low, ans, vertex, time):
		if visited[vertex] == -1:
			visited[vertex] = 1
		disc[vertex] = time + 1
		low[vertex] = time + 1
		for j in adj[vertex]:
			if visited[j] == -1:
				parents[j] = vertex
				self.dfs(V, adj, visited, parents, disc, low, ans, j, time + 1)
				low[vertex] = min(low[vertex], low[j])
				if low[j] > disc[vertex]:
					ans.append(sorted([vertex, j]))
			elif parents[vertex] != j:
				low[vertex] = min(low[vertex], disc[j])

	def criticalConnections(self, V, adj):
		visited = [-1] * V
		parents = [-1] * V
		disc = [sys.maxsize] * V
		low = [sys.maxsize] * V
		ans = []
		for i in range(V):
			time = 0
			if visited[i] == -1:
				self.dfs(V, adj, visited, parents, disc, low, ans, i, time)
		return sorted(ans)


class Solution:

	def dfs(self, adj, node, parent, vis, timer, tin, low, bridges):
		vis[node] = True
		tin[node] = low[node] = timer
		timer += 1
		for v in adj[node]:
			if v == parent:
				continue
			if vis[v] == False:
				self.dfs(adj, v, node, vis, timer, tin, low, bridges)
				low[node] = min(low[node], low[v])
				if low[v] > tin[node]:
					if v < node:
						bridges.append((v, node))
					else:
						bridges.append((node, v))
			else:
				low[node] = min(low[node], low[v])

	def criticalConnections(self, n, adj):
		vis = [False] * n
		timer = 0
		tin = [0] * n
		low = [n + 1] * n
		bridges = []
		for i in range(n):
			if vis[i] == False:
				self.dfs(adj, i, -1, vis, timer, tin, low, bridges)
		bridges = list(set(bridges))
		bridges.sort()
		return bridges


class Solution:

	def criticalConnections(self, V, adj):
		visited = [0] * V
		tin = [0] * V
		low = [0] * V
		timer = 1
		bridges = []
		self.dfs(0, -1, visited, low, tin, adj, bridges, timer)
		bridges.sort()
		return bridges

	def dfs(self, node, parent, visited, low, tin, adj, bridges, timer):
		visited[node] = 1
		low[node] = tin[node] = timer
		timer += 1
		for neigh in adj[node]:
			if neigh == parent:
				continue
			if visited[neigh] == 0:
				self.dfs(neigh, node, visited, low, tin, adj, bridges, timer)
				low[node] = min(low[node], low[neigh])
				if low[neigh] > tin[node]:
					if neigh < node:
						bridges.append([neigh, node])
					else:
						bridges.append([node, neigh])
			else:
				low[node] = min(low[node], low[neigh])


time = 0

def bridgeutil(graph, v, disc, low, parent, ans):
	global time
	disc[v] = time
	low[v] = time
	time += 1
	for i in graph[v]:
		if disc[i] == -1:
			parent[i] = v
			bridgeutil(graph, i, disc, low, parent, ans)
			if low[i] > disc[v]:
				ans.append(sorted((v, i)))
			low[v] = min(low[v], low[i])
		elif i != parent[v]:
			low[v] = min(low[v], low[i])

def bridge(graph):
	disc = [-1] * len(graph)
	low = [-1] * len(graph)
	parent = [-1] * len(graph)
	ans = []
	bridgeutil(graph, 0, disc, low, parent, ans)
	return ans

class Solution:

	def criticalConnections(self, V, adj):
		return sorted(bridge(adj))


def dfs(node, visited, parent, t_in, t_low, timer, bridges):
	visited[node] = True
	t_in[node] = timer[0]
	t_low[node] = timer[0]
	timer[0] += 1
	for neigh in adj[node]:
		if not visited[neigh]:
			parent[neigh] = node
			dfs(neigh, visited, parent, t_in, t_low, timer, bridges)
			t_low[node] = min(t_low[node], t_low[neigh])
			if t_low[neigh] > t_in[node]:
				bridges.append(tuple(sorted((node, neigh))))
		elif visited[neigh] and parent[node] != neigh:
			t_low[node] = min(t_low[node], t_low[neigh])

class Solution:

	def criticalConnections(self, V, adj):
		visited = [False for i in range(V)]
		parent = [-1 for i in range(V)]
		t_in = [0 for i in range(V)]
		t_low = [0 for i in range(V)]
		timer = [1]
		bridges = []
		dfs(0, visited, parent, t_in, t_low, timer, bridges)
		bridges = list(sorted(bridges))
		return bridges


class Solution:

	def criticalConnections(self, v, adj):
		bridges = []
		time = 0

		def dfs(d, source, visited, parent, disc, low):
			nonlocal time, bridges
			visited[source] = True
			disc[source] = time
			low[source] = time
			time += 1
			for j in d[source]:
				if visited[j] == False:
					parent[j] = source
					dfs(d, j, visited, parent, disc, low)
					low[source] = min(low[source], low[j])
					if low[j] > disc[source]:
						bridges.append((min(j, source), max(j, source)))
				elif j != parent[source]:
					low[source] = min(low[source], disc[j])
		visited = [False] * v
		parent = [-1] * v
		disc = [float('inf')] * v
		low = [float('inf')] * v
		for i in range(v):
			if visited[i] == False:
				dfs(adj, i, visited, parent, disc, low)
		return sorted(bridges)


class Solution:

	def find_cut_edges(self, u, adj, disc, low, time, parents, res):
		time[0] += 1
		disc[u] = time[0]
		low[u] = time[0]
		for v in adj[u]:
			if disc[v] == -1:
				parents[v] = u
				self.find_cut_edges(v, adj, disc, low, time, parents, res)
				low[u] = min(low[u], low[v])
				if disc[u] < low[v]:
					if u < v:
						res.append([u, v])
					else:
						res.append([v, u])
			elif v != parents[u]:
				low[u] = min(low[u], disc[v])

	def criticalConnections(self, V, adj):
		disc = [-1] * V
		low = [-1] * V
		time = [0]
		parents = [-1] * V
		res = []
		for u in range(V):
			if disc[u] == -1:
				self.find_cut_edges(u, adj, disc, low, time, parents, res)
		res.sort()
		return res


class Solution:

	def criticalConnections(self, V, adj):
		self.timer = 1
		visited = [0] * V
		lowTime = [0] * V
		timeInsertion = [0] * V
		bridge = set()
		for i in range(V):
			if visited[i] == 0:
				self.dfs(i, -1, adj, visited, lowTime, timeInsertion, bridge)
		s = list(bridge)
		return sorted(s)

	def dfs(self, node, parent, adj, visited, lowTime, timeInsertion, bridge):
		visited[node] = 1
		(lowTime[node], timeInsertion[node]) = (self.timer, self.timer)
		self.timer += 1
		for it in adj[node]:
			if it == parent:
				continue
			if visited[it] == 0:
				self.dfs(it, node, adj, visited, lowTime, timeInsertion, bridge)
				lowTime[node] = min(lowTime[it], lowTime[node])
				if lowTime[it] > timeInsertion[node]:
					if it < node:
						bridge.add((it, node))
					else:
						bridge.add((node, it))
			else:
				lowTime[node] = min(lowTime[it], lowTime[node])


class Solution:

	def dfs(self, adj, disc, low, parent, visited, time, node, ans):
		visited[node] = True
		disc[node] = time
		low[node] = time
		for i in adj[node]:
			if i == parent[node]:
				continue
			elif visited[i] == False:
				parent[i] = node
				if self.dfs(adj, disc, low, parent, visited, time + 1, i, ans):
					return 1
				low[node] = min(low[node], low[i])
				if low[i] > disc[node]:
					if i < node:
						ans.append([i, node])
					else:
						ans.append([node, i])
			else:
				low[node] = min(low[node], low[i])

	def criticalConnections(self, V, adj):
		ans = []
		disc = [-1] * V
		low = [-1] * V
		visited = [False] * V
		parent = [-1] * V
		for i in range(V):
			if visited[i] == False:
				self.dfs(adj, disc, low, parent, visited, 0, i, ans)
		return sorted(ans)


class Solution:

	def criticalConnections(self, V, adj):

		def dfs(node, par, adj, vis, tin, low, timer, ans):
			vis[node] = 1
			tin[node] = timer + 1
			low[node] = timer + 1
			for ele in adj[node]:
				if ele == par:
					continue
				if not vis[ele]:
					dfs(ele, node, adj, vis, tin, low, timer + 1, ans)
					low[node] = min(low[node], low[ele])
					if low[ele] > tin[node]:
						ans += [[min(node, ele), max(node, ele)]]
				else:
					low[node] = min(low[node], tin[ele])
		vis = [0] * V
		tin = [0] * V
		low = [0] * V
		ans = []
		dfs(0, -1, adj, vis, tin, low, 0, ans)
		ans.sort()
		return ans


class Solution:

	def execute_dfs(self, V, adj, s):
		global visited
		global times
		global parents
		global low
		global global_time
		global bridges
		visited[s] = True
		times[s] = global_time
		low[s] = global_time
		global_time += 1
		for node in adj[s]:
			if visited[node] == False:
				parents[node] = s
				self.execute_dfs(V, adj, node)
				low[s] = min(low[s], low[node])
				if low[node] > times[s]:
					bridges.add((min(node, s), max(node, s)))
			elif parents[s] != node:
				low[s] = min(low[s], times[node])

	def dfs(self, V, adj):
		global visited
		global times
		global parents
		global low
		global global_time
		global bridges
		global_time = 0
		bridges = set()
		visited = []
		times = []
		parents = []
		low = []
		for i in range(V):
			visited.append(False)
			times.append(float('inf'))
			parents.append(i)
			low.append(float('inf'))
		for i in range(V):
			if visited[i] == False:
				self.execute_dfs(V, adj, i)
		return bridges

	def criticalConnections(self, V, adj):
		ans = self.dfs(V, adj)
		ans = sorted(ans, key=lambda item: (item[0], item[1]))
		return ans


class Solution:

	def __init__(self):
		self.visited = []
		self.out = []
		self.low = []
		self.dis = []
		self.parent = []
		self.adj = None
		self.time = 0

	def rec(self, u):
		self.visited[u] = True
		self.low[u] = self.time
		self.dis[u] = self.time
		self.time += 1
		for v in self.adj[u]:
			if self.visited[v] == False:
				self.parent[v] = u
				self.rec(v)
				self.low[u] = min(self.low[u], self.low[v])
				if self.low[v] > self.dis[u]:
					if v > u:
						self.out.append([u, v])
					else:
						self.out.append([v, u])
			elif self.parent[u] != v:
				self.low[u] = min(self.low[u], self.dis[v])

	def criticalConnections(self, V, adj):
		self.visited = [False] * V
		self.low = [float('inf')] * V
		self.dis = [float('inf')] * V
		self.adj = adj
		self.parent = [-1] * V
		for i in range(V):
			if self.visited[i] == False:
				self.rec(i)
		self.out.sort()
		return self.out


class Solution:

	def criticalConnections(self, n, x):
		t = 0
		se = set()
		v = set()
		disc = {}
		low = {}

		def f(i, p=-1):
			nonlocal t
			t += 1
			disc[i] = t
			low[i] = t
			v.add(i)
			child = 0
			for j in x[i]:
				if j != p:
					if j not in v:
						f(j, i)
						low[i] = min(low[i], low[j])
						if low[j] > disc[i]:
							se.add((min(i, j), max(i, j)))
					else:
						low[i] = min(low[i], disc[j])
		for i in range(n):
			if i not in v:
				f(i)
		return sorted(list(se))


class Solution:

	def criticalConnections(self, V, adj):
		self.id = 1
		vis = [0] * V
		low = [float('inf')] * V

		def dfs(i=0, prev=None):
			vis[i] = self.id
			low[i] = self.id
			self.id += 1
			for nei in adj[i]:
				if nei == prev:
					continue
				if not vis[nei]:
					dfs(nei, i)
				low[i] = min(low[i], low[nei])
		for i in range(V):
			if not vis[i]:
				dfs(i)
		ans = []
		for i in range(V):
			for nei in adj[i]:
				if nei < i:
					continue
				if low[nei] > vis[i] or low[i] > vis[nei]:
					ans.append((i, nei))
		ans.sort()
		return ans
import sys
sys.setrecursionlimit(10 ** 6)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(V, E) = map(int, input().split())
		adj = [[] for i in range(V)]
		for _ in range(E):
			(u, v) = map(int, input().split())
			adj[u].append(v)
			adj[v].append(u)
		obj = Solution()
		ans = obj.criticalConnections(V, adj)
		for i in range(len(ans)):
			print(ans[i][0], ans[i][1])


class Solution:

	def criticalConnections(self, V, adj):
		parent = [-1 for i in range(V)]
		disc = [-1 for i in range(V)]
		low = [-1 for i in range(V)]
		time = [-1]
		edges = []

		def solver(v):
			time[0] += 1
			disc[v] = time[0]
			low[v] = time[0]
			child = 0
			mn = low[v]
			for k in adj[v]:
				if disc[k] == -1:
					parent[k] = v
					child += 1
					t = solver(k)
					if t > disc[v]:
						if v > k:
							edges.append([k, v])
						else:
							edges.append([v, k])
					mn = min(mn, t)
				elif parent[v] != k:
					mn = min(mn, disc[k])
				else:
					continue
			low[v] = mn
			return low[v]
		for i in range(V):
			if disc[i] == -1:
				solver(i)
		edges.sort()
		return edges
import sys
sys.setrecursionlimit(10 ** 6)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(V, E) = map(int, input().split())
		adj = [[] for i in range(V)]
		for _ in range(E):
			(u, v) = map(int, input().split())
			adj[u].append(v)
			adj[v].append(u)
		obj = Solution()
		ans = obj.criticalConnections(V, adj)
		for i in range(len(ans)):
			print(ans[i][0], ans[i][1])


class Solution:

	def criticalConnections(self, n, adj):
		ind = [0 for i in range(n)]
		low = [0 for i in range(n)]
		vis = [False for i in range(n)]
		ct = [0]
		ans = []

		def dfs(d, vis, pa):
			ind[d] = low[d] = ct[0]
			ct[0] += 1
			vis[d] = True
			for val in adj[d]:
				if val == pa:
					continue
				elif vis[val]:
					low[d] = min(low[d], ind[val])
				else:
					dfs(val, vis, d)
					if low[val] > ind[d]:
						if d < val:
							te = (d, val)
						else:
							te = (val, d)
						ans.append(te)
					low[d] = min(low[d], low[val])
		for i in range(n):
			if not vis[i]:
				dfs(i, vis, -1)
		return sorted(ans)


class Solution:

	def criticalConnections(self, V, adj):
		global t
		t = 0
		time = [0 for i in range(V)]
		low = [0 for i in range(V)]
		vis = [0 for i in range(V)]

		def dfs(n, par):
			global t
			t += 1
			time[n] = t
			low[n] = t
			vis[n] = 1
			for j in adj[n]:
				if j == par:
					continue
				elif vis[j] == 0:
					dfs(j, n)
					low[n] = min(low[j], low[n])
					if low[j] > time[n]:
						ans.append(sorted([n, j]))
				else:
					low[n] = min(low[n], time[j])
		ans = []
		for i in range(V):
			if vis[i] == 0:
				dfs(i, -1)
		ans.sort()
		return ans


class Solution:

	def criticalConnections(self, n, adj):
		ans = []
		self.time = 0
		self.d = adj

		def dfs(node, parent, vis, tin, low):
			vis[node] = 1
			tin[node] = low[node] = self.time
			self.time += 1
			for child in self.d[node]:
				if child == parent:
					continue
				elif vis[child] == 0:
					dfs(child, node, vis, tin, low)
					low[node] = min(low[node], low[child])
					if low[child] > tin[node]:
						ans.append(sorted([node, child]))
				else:
					low[node] = min(low[node], tin[child])
		v = [0 for _ in range(n)]
		low = [float('inf') for _ in range(n)]
		tin = [float('inf') for _ in range(n)]
		for i in range(n):
			if v[i] == 0:
				dfs(i, -1, v, tin, low)
		return sorted(ans)


class Solution:

	def criticalConnections(self, V, adj):
		critical_conn = []
		arrival_time = [0] * V
		lowest_time = [0] * V
		visited = [False] * V

		def dfs(node, parent, timer):
			visited[node] = True
			arrival_time[node] = timer + 1
			lowest_time[node] = timer + 1
			timer += 1
			for it in adj[node]:
				if it == parent:
					continue
				if visited[it] == True:
					lowest_time[node] = min(lowest_time[node], lowest_time[it])
					continue
				dfs(it, node, timer)
				lowest_time[node] = min(lowest_time[node], lowest_time[it])
				if arrival_time[node] < lowest_time[it]:
					critical_conn.append([min(node, it), max(node, it)])
		dfs(0, -1, 0)
		return sorted(critical_conn)


class Solution:

	def criticalConnections(self, V, adj):
		critical_conn = []
		arrival_time = [0] * V
		lowest_time = [0] * V
		visited = [False] * V

		def dfs(node, parent, timer):
			visited[node] = True
			arrival_time[node] = timer + 1
			lowest_time[node] = timer + 1
			timer += 1
			for it in adj[node]:
				if it != parent:
					if visited[it] == False:
						dfs(it, node, timer)
						lowest_time[node] = min(lowest_time[node], lowest_time[it])
						if arrival_time[node] < lowest_time[it]:
							critical_conn.append(sorted([node, it]))
					else:
						lowest_time[node] = min(lowest_time[node], lowest_time[it])
		dfs(0, -1, 0)
		critical_conn.sort(key=lambda x: x[1])
		critical_conn.sort(key=lambda x: x[0])
		return critical_conn


class Solution:

	def dfs(self, V, adj, visited, parent, disc, low, critical, ind):
		visited[ind] = True
		disc[ind] = self.k
		low[ind] = self.k
		self.k += 1
		for i in adj[ind]:
			if not visited[i]:
				parent[i] = ind
				self.dfs(V, adj, visited, parent, disc, low, critical, i)
				if low[i] > disc[ind]:
					critical.append((min(ind, i), max(ind, i)))
				low[ind] = min(low[ind], low[i])
			elif parent[ind] != i:
				low[ind] = min(low[ind], disc[i])

	def criticalConnections(self, V, adj):
		visited = [False] * V
		parent = [-1] * V
		disc = [-1] * V
		low = [-1] * V
		self.k = 0
		critical = list()
		self.dfs(V, adj, visited, parent, disc, low, critical, 0)
		critical.sort(key=lambda x: x[1])
		critical.sort(key=lambda x: x[0])
		return critical


class Solution:

	def dfs(self, node, parent, timer, graph, inTime, lowTime, conn):
		inTime[node] = timer
		lowTime[node] = timer
		timer += 1
		for nbr in graph[node]:
			if nbr == parent:
				continue
			if inTime[nbr] != -1:
				lowTime[node] = min(lowTime[node], inTime[nbr])
				continue
			self.dfs(nbr, node, timer, graph, inTime, lowTime, conn)
			lowTime[node] = min(lowTime[node], lowTime[nbr])
			if lowTime[nbr] > inTime[node]:
				c = [min(node, nbr), max(node, nbr)]
				conn.append(c)

	def criticalConnections(self, n, graph):
		inTime = [-1] * n
		lowTime = [-1] * n
		conn = []
		self.dfs(0, -1, 0, graph, inTime, lowTime, conn)
		return sorted(conn)


class Solution:

	def criticalConnections(self, V, adj):

		def dfs(node, parent, timer, disc, low, visited, adj, result):
			visited[node] = True
			disc[node] = low[node] = timer
			timer += 1
			for nei in adj[node]:
				if nei == parent:
					continue
				if not visited[nei]:
					dfs(nei, node, timer, disc, low, visited, adj, result)
					low[node] = min(low[node], low[nei])
					if low[nei] > disc[node]:
						if nei > node:
							result.append([node, nei])
						else:
							result.append([nei, node])
				else:
					low[node] = min(low[node], low[nei])
		disc = [V] * V
		low = [V] * V
		parent = -1
		timer = 0
		visited = [False] * V
		result = []
		for i in range(V):
			if not visited[i]:
				dfs(i, parent, timer, disc, low, visited, adj, result)
		return sorted(result)


class Solution:

	def criticalConnections(self, V, adj):
		vis = set()
		tin = [0] * V
		low = [0] * V
		res = []

		def dfs(node, parent, timer):
			vis.add(node)
			tin[node] = timer
			low[node] = timer
			timer += 1
			for neigh in adj[node]:
				if neigh == parent:
					continue
				if neigh not in vis:
					dfs(neigh, node, timer)
					low[node] = min(low[node], low[neigh])
					if low[neigh] > tin[node]:
						res.append((min(neigh, node), max(neigh, node)))
				else:
					low[node] = min(low[node], tin[neigh])
		timer = 0
		for i in range(V):
			if i not in vis:
				dfs(i, -1, timer)
		res.sort()
		return res


class Solution:

	def criticalConnections(self, n, adj):
		global low, disc, time, ans
		ans = []
		time = 0
		low = [-1 for i in range(n)]
		disc = [-1 for i in range(n)]
		for i in range(n):
			if disc[i] == -1:
				dfs(adj, i, -1)
		ans.sort()
		return ans

def dfs(adj, u, b):
	global time, ans
	disc[u] = time
	low[u] = time
	for v in adj[u]:
		time += 1
		if disc[v] == -1:
			dfs(adj, v, u)
			low[u] = min(low[u], low[v])
			if low[v] > disc[u]:
				a = [u, v]
				a.sort()
				ans.append(a)
		elif v != b:
			low[u] = min(low[u], disc[v])


class Solution:

	def criticalConnections(self, n, adj):
		self.t = 1
		self.low = [0] * n
		self.dis = [0] * n
		self.ans = []

		def dfs(i, par):
			self.low[i] = self.dis[i] = self.t
			self.t += 1
			for j in adj[i]:
				if not self.dis[j]:
					dfs(j, i)
					self.low[i] = min(self.low[i], self.low[j])
				elif j != par:
					self.low[i] = min(self.low[i], self.dis[j])
				if self.dis[i] < self.low[j]:
					self.ans.append([min(i, j), max(i, j)])
		for i in range(n):
			if self.dis[i] == 0:
				dfs(i, -1)
		return sorted(self.ans)


class Solution:

	def criticalConnections(self, V, adj):
		parent = [-1] * V
		depth = [-1] * V
		low = [-1] * V
		u_id = [0]
		bridges = []
		self.dfs(0, adj, u_id, depth, low, parent, bridges)
		bridges.sort(key=lambda x: (x[0], x[1]))
		return bridges

	def dfs(self, v, adj, u_id, depth, low, parent, bridges):
		depth[v] = u_id[0]
		low[v] = u_id[0]
		u_id[0] += 1
		for u in adj[v]:
			if depth[u] == -1:
				parent[u] = v
				self.dfs(u, adj, u_id, depth, low, parent, bridges)
				low[v] = min(low[u], low[v])
				if depth[v] < low[u]:
					bridges.append([min(v, u), max(v, u)])
			elif parent[v] != u:
				low[v] = min(low[v], depth[u])
		return


class Solution:

	def criticalConnections(self, V, adj):
		critical = set()
		for i in range(V):
			for j in adj[i]:
				pair = (min(i, j), max(i, j))
				if pair not in critical:
					critical.add(pair)
		rank = [-1] * V

		def dfs(node, parent, time):
			rank[node] = time
			ans = float('inf')
			for nxt in adj[node]:
				if nxt != parent:
					if rank[nxt] == -1:
						remove = dfs(nxt, node, time + 1)
						if remove <= time:
							edge = (min(node, nxt), max(node, nxt))
							if edge in critical:
								critical.remove(edge)
							ans = min(ans, remove)
					else:
						edge = (min(node, nxt), max(node, nxt))
						if edge in critical:
							critical.remove(edge)
						ans = min(ans, rank[nxt])
			return ans
		dfs(0, -1, 0)
		return sorted(list(critical))


class Solution:

	def criticalConnections(self, V, adj):
		self.it = [-1] * V
		self.lt = [-1] * V
		self.timer = 1
		self.ans = []
		for i in range(V):
			if self.it[i] == -1:
				self.dfs(i, -1)
		return sorted(self.ans)

	def dfs(self, source, parent):
		self.it[source] = self.timer
		self.lt[source] = self.timer
		self.timer += 1
		for adjacent in adj[source]:
			if adjacent == parent:
				continue
			elif self.it[adjacent] == -1:
				self.dfs(adjacent, source)
				self.lt[source] = min(self.lt[source], self.lt[adjacent])
				if self.it[source] < self.lt[adjacent]:
					self.ans.append(sorted([source, adjacent]))
			else:
				self.lt[source] = min(self.lt[source], self.it[adjacent])


def dfs(g, u, prev):
	global time
	global pre
	global post
	global res
	pre[u] = time
	post[u] = time
	time = time + 1
	for v in g[u]:
		if pre[v] == -1:
			dfs(g, v, u)
			if post[v] > pre[u]:
				res.append([u, v])
			post[u] = min(post[u], post[v])
		elif v != prev:
			post[u] = min(post[u], pre[v])

def criticalConn(g, n):
	global time
	global pre
	global post
	global res
	res = []
	pre = [-1 for i in range(n)]
	post = [-1 for i in range(n)]
	time = 0
	dfs(g, 0, 0)
	for i in res:
		i.sort()
	res.sort()
	return res

class Solution:

	def criticalConnections(self, V, adj):
		return criticalConn(adj, V)


class Solution:

	def __init__(self):
		self.timer = 0

	def dfs(self, node, par, vis, tin, low, adj, bridges):
		vis[node] = True
		tin[node] = low[node] = self.timer
		self.timer += 1
		for k in adj[node]:
			if k == par:
				continue
			if not vis[k]:
				self.dfs(k, node, vis, tin, low, adj, bridges)
				low[node] = min(low[node], low[k])
				if low[k] > tin[node]:
					bridges.append([min(k, node), max(k, node)])
			else:
				low[node] = min(low[node], tin[k])
		return None

	def criticalConnections(self, V, adj):
		vis = [False] * V
		tin = [-1] * V
		low = [-1] * V
		bridges = []
		for x in range(V):
			if not vis[x]:
				self.dfs(x, -1, vis, tin, low, adj, bridges)
		bridges.sort()
		return bridges


from collections import defaultdict

class Solution:

	def criticalConnections(self, V, graph):

		def dfs(u, ap, time):
			dis[u] = time
			low[u] = time
			time = time + 1
			visited[u] = True
			for v in graph[u]:
				if parent[u] == v:
					continue
				elif visited[v] is True:
					low[u] = min(low[u], dis[v])
				else:
					parent[v] = u
					dfs(v, ap, time)
					low[u] = min(low[u], low[v])
					if low[v] > dis[u]:
						if u < v:
							ap.append([u, v])
						else:
							ap.append([v, u])
		parent = [-1] * V
		dis = [-1] * V
		low = [-1] * V
		visited = [False] * V
		ap = []
		dfs(0, ap, 0)
		return sorted(ap, key=lambda x: (x[0], x[1]))