Given an undirected graph (not necessarily connected) with V vertices and adjacency list adj. You are required to find all the vertices removing which (and edges through it) disconnects the graph into 2 or more components, or in other words, removing which increases the number of connected components.
Note: Indexing is zero-based i.e nodes numbering from (0 to V-1). There might be loops present in the graph.
Example 1:
Input:
Output:{1,4}
Explanation: Removing the vertex 1 will
discconect the graph as-
Removing the vertex 4 will disconnect the
graph as-
 
Your Task:
You don't need to read or print anything. Your task is to complete the function articulationPoints() which takes V and adj as input parameters and returns a list containing all the vertices removing which turn the graph into two or more disconnected components in sorted order. If there are no such vertices then returns a list containing -1.
 
Expected Time Complexity: O(V + E)
Expected Auxiliary Space: O(V)
 
Constraints:
1 ≤ V ≤ 10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Data structures

Starter code: class Solution:
	def articulationPoints(self, V, adj):
		#Code here

Solutions:
import sys
sys.setrecursionlimit(10 ** 6)
from math import inf

class Solution:

	def articulationPoints(self, V, adj):
		visited = [0] * V
		tin = [inf] * V
		low = [inf] * V
		mark = set()
		timer = 1

		def dfs(node, par):
			nonlocal timer
			visited[node] = 1
			tin[node] = low[node] = timer
			timer += 1
			child = 0
			for each in adj[node]:
				if not visited[each]:
					dfs(each, node)
					low[node] = min(low[node], low[each])
					if low[each] >= tin[node] and par != -1:
						mark.add(node)
					child += 1
				else:
					low[node] = min(low[node], tin[each])
			if child > 1 and par == -1:
				mark.add(node)
		ans = []
		for i in range(V):
			if not visited[i]:
				dfs(i, -1)
		return sorted(list(mark)) if mark else [-1]


class Solution:

	def articulationPoints(self, V, adj):
		global timer
		timer = 0
		dis = [0] * V
		low = [0] * V
		visited = [False] * V
		ap = [False] * V
		parent = [None] * V
		res = []
		for i in range(V):
			if visited[i] == False:
				self.fun(i, dis, low, ap, V, adj, visited, parent)
		res = []
		flag = 0
		for i in range(V):
			if ap[i] == True:
				res.append(i)
				flag = 1
		if flag == 0:
			return [-1]
		return res

	def fun(self, u, dis, low, ap, V, adj, visited, parent):
		global timer
		visited[u] = True
		timer = timer + 1
		dis[u] = timer
		low[u] = timer
		children = 0
		for v in adj[u]:
			if visited[v] == False:
				children += 1
				parent[v] = u
				self.fun(v, dis, low, ap, V, adj, visited, parent)
				low[u] = min(low[u], low[v])
				if parent[u] == None and children > 1:
					ap[u] = True
				if parent[u] != None and low[v] >= dis[u]:
					ap[u] = True
			elif v != parent[u]:
				low[u] = min(low[u], dis[v])


class Solution:

	def APUtil(self, u, visited, ap, parent, low, disc, adj, time):
		children = 0
		visited[u] = True
		disc[u] = time
		low[u] = time
		time += 1
		for v in adj[u]:
			if visited[v] == False:
				parent[v] = u
				children += 1
				self.APUtil(v, visited, ap, parent, low, disc, adj, time)
				low[u] = min(low[u], low[v])
				if parent[u] == -1 and children > 1:
					ap[u] = True
				if parent[u] != -1 and low[v] >= disc[u]:
					ap[u] = True
			elif v != parent[u]:
				low[u] = min(low[u], disc[v])

	def articulationPoints(self, V, adj):
		visited = [False] * V
		disc = [float('Inf')] * V
		low = [float('Inf')] * V
		parent = [-1] * V
		ap = [False] * V
		time = 0
		for i in range(V):
			if visited[i] == False:
				self.APUtil(i, visited, ap, parent, low, disc, adj, time)
		flag = 0
		ans = []
		for (index, value) in enumerate(ap):
			if value == True:
				flag = 1
				ans.append(index)
		if flag == 0:
			return [-1]
		else:
			return ans


class Solution:

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

				def dfs(j, vis, t1, t2, par, ap, time):
					child = 0
					for k in adj[j]:
						if k not in vis:
							time += 1
							child += 1
							vis.add(k)
							t1[k] = t2[k] = time
							par[k] = j
							dfs(k, vis, t1, t2, par, ap, time)
							t2[j] = min(t2[j], t2[k])
							if t2[k] >= t1[j] and par[j] != -1:
								ap.add(j)
						elif par[j] != k:
							t2[j] = min(t2[j], t1[k])
					if child > 1 and par[j] == -1:
						ap.add(j)
				dfs(i, vis, t1, t2, par, ap, time)
		if len(ap) == 0:
			return [-1]
		return sorted(list(ap))


class Solution:

	def articulationPoints(self, V, adj):
		id = 0
		outEdges = 0
		low = {}
		ids = {}
		visited = set()
		arts = set()

		def dfs(root, node, par):
			nonlocal outEdges, id
			if par == root:
				outEdges += 1
			visited.add(node)
			id += 1
			low[node] = id
			ids[node] = id
			for nextV in adj[node]:
				if nextV == par:
					continue
				if nextV not in visited:
					dfs(root, nextV, node)
					low[node] = min(low[node], low[nextV])
					if ids[node] <= low[nextV]:
						arts.add(node)
				else:
					low[node] = min(low[node], ids[nextV])
			return
		for i in range(V):
			if i not in visited:
				outEdges = 0
				dfs(i, i, -1)
				if outEdges > 1:
					arts.add(i)
				elif i in arts:
					arts.remove(i)
		ans = [-1]
		if len(arts) > 0:
			ans = list(arts)
			ans.sort()
		return ans


class Solution:

	def __init__(self):
		self.l1 = []
		self.h = {}
		self.c1 = 1

	def articulationPoints(self, V, adj):
		v = [-1] * V
		v1 = [-1] * V
		(t, l) = ([-1] * V, [-1] * V)
		(t[0], l[0]) = (1, 1)
		for i in range(V):
			if v[i] == -1:
				self.solve(adj, v, i, t, l, -1)
				self.c1 = 0
				self.dfs(adj, i, v1, i)
				if self.c1 >= 2:
					self.l1 += [i]
		self.l1.sort()
		if len(self.l1) == 0:
			return [-1]
		return self.l1

	def solve(self, adj, v, i, t, l, p):
		v[i] = 1
		for j in adj[i]:
			if v[j] == -1:
				t[j] = self.c1 + 1
				l[j] = t[j]
				self.c1 += 1
				self.solve(adj, v, j, t, l, i)
				l[i] = min(l[i], l[j])
				if l[j] >= t[i] and p != -1:
					if self.h.get(i, -1) == -1:
						self.l1 += [i]
						self.h[i] = 1
			elif j != p:
				l[i] = min(l[i], t[j])

	def dfs(self, adj, i, v1, p):
		v1[i] = 1
		for j in adj[i]:
			if v1[j] == -1:
				if i == p:
					self.c1 += 1
				self.dfs(adj, j, v1, p)


class Solution:

	def articulationPoints(self, V, adj):
		timer = 0
		disc = [-1] * V
		low = [-1] * V
		visited = [False] * V
		parent = -1
		result = [0] * V
		for i in range(V):
			if not visited[i]:
				self.dfs(i, parent, timer, disc, low, result, adj, visited)
		articulate_pt = []
		for i in range(V):
			if result[i]:
				articulate_pt.append(i)
		if len(articulate_pt) == 0:
			return [-1]
		return articulate_pt

	def dfs(self, node, parent, timer, disc, low, result, adj, visited):
		visited[node] = True
		timer += 1
		disc[node] = low[node] = timer
		child = 0
		for i in adj[node]:
			if i == parent:
				continue
			if not visited[i]:
				self.dfs(i, node, timer, disc, low, result, adj, visited)
				low[node] = min(low[node], low[i])
				if low[i] >= disc[node] and parent != -1:
					result[node] = 1
				child += 1
			else:
				low[node] = min(low[node], disc[i])
		if parent == -1 and child > 1:
			result[node] = 1


class Solution:

	def dfs(self, node, parent, timer, adj, visited, low, tin, arti):
		visited[node] = True
		timer += 1
		low[node] = tin[node] = timer
		child = 0
		for it in adj[node]:
			if not visited[it]:
				self.dfs(it, node, timer, adj, visited, low, tin, arti)
				low[node] = min(low[node], low[it])
				if low[it] >= tin[node] and parent != -1:
					arti[node] = 1
				child += 1
			elif it != parent:
				low[node] = min(low[node], tin[it])
		if child > 1 and parent == -1:
			arti[node] = 1

	def articulationPoints(self, V, adj):
		visited = [False] * V
		low = [-1] * V
		tin = [-1] * V
		arti = [0] * V
		timer = 0
		for i in range(V):
			if not visited[i]:
				self.dfs(i, -1, timer, adj, visited, low, tin, arti)
		ans = sorted([idx for idx in range(V) if arti[idx] == 1])
		if not ans:
			return [-1]
		return ans


import sys
sys.setrecursionlimit(100000000)
time = 0

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

def articulation(graph):
	disc = [-1] * len(graph)
	low = [-1] * len(graph)
	parent = [-1] * len(graph)
	ans = []
	for i in range(len(graph)):
		if disc[i] == -1:
			articulationutil(graph, i, disc, low, parent, ans)
	return list(set(ans))

class Solution:

	def articulationPoints(self, V, adj):
		a = sorted(articulation(adj))
		if a == []:
			return [-1]
		return a


import sys
sys.setrecursionlimit(10 ** 6)

def dfs(i, visit, low, disc, parent, time, adj, ap):
	visit[i] = 1
	disc[i] = time
	low[i] = time
	child = 0
	time += 1
	for v in adj[i]:
		if visit[v] == 0:
			parent[v] = i
			child += 1
			dfs(v, visit, low, disc, parent, time, adj, ap)
			low[i] = min(low[i], low[v])
			if parent[i] == -1 and child > 1:
				ap[i] = 1
			if parent[i] != -1 and low[v] >= disc[i]:
				ap[i] = 1
		elif parent[v] != i:
			low[i] = min(low[i], disc[v])

class Solution:

	def articulationPoints(self, V, adj):
		if V == 1 or V == 2:
			return [-1]
		visit = [0 for _ in range(V)]
		low = [float('inf') for _ in range(V)]
		disc = [float('inf') for _ in range(V)]
		parent = [-1 for _ in range(V)]
		ap = [0 for _ in range(V)]
		ans = []
		for i in range(V):
			if visit[i] == 0:
				dfs(i, visit, low, disc, parent, 0, adj, ap)
		for i in range(V):
			if ap[i] == 1:
				ans.append(i)
		if len(ans) == 0:
			return [-1]
		return ans


class Solution:

	def check(self, time, ap, disc, low, vis, adj, u, p):
		low[u] = time[0]
		disc[u] = time[0]
		time[0] += 1
		vis[u] = 1
		child = 0
		for i in adj[u]:
			if vis[i] == 0:
				self.check(time, ap, disc, low, vis, adj, i, u)
				child += 1
				if p != -1 and low[i] >= disc[u]:
					ap[u] = 1
				low[u] = min(low[u], low[i])
			elif vis[i] == 1 and i != p:
				low[u] = min(low[u], disc[i])
		if p == -1 and child > 1:
			ap[u] = 1

	def articulationPoints(self, v, adj):
		time = [0]
		ap = [0] * v
		disc = [0] * v
		low = [0] * v
		vis = [0] * v
		ans = []
		for i in range(v):
			if vis[i] == 0:
				self.check(time, ap, disc, low, vis, adj, i, -1)
		for x in range(len(ap)):
			if ap[x] == 1:
				ans.append(x)
		return ans if len(ans) > 0 else [-1]


time = 0

class Solution:

	def APUtil(self, node, visited, apNode, parent, disc, low, adj):
		global time
		child = 0
		visited[node] = True
		disc[node] = time
		low[node] = time
		time += 1
		for i in adj[node]:
			if visited[i] == False:
				parent[i] = node
				child += 1
				self.APUtil(i, visited, apNode, parent, disc, low, adj)
				low[node] = min(low[node], low[i])
				if parent[node] == -1 and child > 1:
					apNode[node] = True
				if parent[node] != -1 and low[i] >= disc[node]:
					apNode[node] = True
			elif i != parent[node]:
				low[node] = min(low[node], disc[i])

	def articulationPoints(self, V, adj):
		visited = [False] * V
		disc = [float('Inf')] * V
		low = [float('Inf')] * V
		parent = [-1] * V
		apNode = [False] * V
		for i in range(V):
			if visited[i] == False:
				self.APUtil(i, visited, apNode, parent, disc, low, adj)
		out = []
		for i in range(V):
			if apNode[i]:
				out.append(i)
		return out if len(out) > 0 else [-1]


class Solution:

	def dfs(self, i, adj, di, lo, ap, pa, l1):
		ch = 0
		lo[i] = l1[0]
		di[i] = l1[0]
		l1[0] += 1
		for x in adj[i]:
			if di[x] == -1:
				ch += 1
				pa[x] = i
				self.dfs(x, adj, di, lo, ap, pa, l1)
				lo[i] = min(lo[i], lo[x])
				if pa[i] == -1 and ch > 1:
					ap[i] = True
				if pa[i] != -1 and lo[x] >= di[i]:
					ap[i] = True
			elif x != pa[i]:
				lo[i] = min(lo[i], lo[x])

	def articulationPoints(self, V, adj):
		di = [-1] * V
		lo = [-1] * V
		ap = [False] * V
		pa = [-1] * V
		l = []
		l1 = [0]
		for i in range(V):
			if di[i] == -1:
				self.dfs(i, adj, di, lo, ap, pa, l1)
		for i in range(V):
			if ap[i]:
				l.append(i)
		if len(l) == 0:
			l = [-1]
		return l


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:
	time = 0

	def dfs(self, arr, u, parent, low, disc, vis, ap):
		disc[u] = low[u] = self.time
		self.time += 1
		ch = 0
		vis[u] = 1
		if not arr[u]:
			return
		else:
			for v in arr[u]:
				if vis[v] == 0:
					parent[v] = u
					ch += 1
					self.dfs(arr, v, parent, low, disc, vis, ap)
					low[u] = min(low[u], low[v])
					if parent[u] == -1 and ch > 1:
						ap.add(u)
					elif parent[u] != -1 and low[v] >= disc[u]:
						ap.add(u)
				elif v != parent[u]:
					low[u] = min(low[u], disc[v])

	def articulationPoints(self, V, arr):
		vis = [0] * V
		ap = set()
		low = [0] * V
		disc = [0] * V
		time = 0
		parent = [-1] * V
		for i in range(V):
			if vis[i] == 0:
				self.dfs(arr, i, parent, low, disc, vis, ap)
		vec = list(ap)
		if len(vec) == 0:
			vec.append(-1)
		return sorted(vec)


class Solution:

	def articulationPoints(self, V, graph):
		visited = [False for _ in range(len(graph))]
		d_time = [-1 for _ in range(len(graph))]
		lowVal = [-1 for _ in range(len(graph))]
		timer = 0
		articulationPoints = set()
		for i in range(len(graph)):
			if not visited[i]:
				self.dfs_articulation(graph, i, visited, -1, d_time, lowVal, timer, articulationPoints)
		return sorted(list(articulationPoints)) if list(articulationPoints) != [] else [-1]

	def dfs_articulation(self, graph, ver, visited, parent, d_time, lowVal, timer, articulationPoints):
		visited[ver] = True
		d_time[ver] = timer + 1
		lowVal[ver] = timer + 1
		children = 0
		for x in graph[ver]:
			if visited[x] and x != parent:
				lowVal[ver] = min(lowVal[ver], d_time[x])
			elif not visited[x]:
				self.dfs_articulation(graph, x, visited, ver, d_time, lowVal, timer + 1, articulationPoints)
				lowVal[ver] = min(lowVal[ver], lowVal[x])
				if lowVal[x] >= d_time[ver] and parent != -1:
					articulationPoints.add(ver)
				children += 1
		if parent == -1 and children > 1:
			articulationPoints.add(ver)


class Solution:

	def __init__(self):
		self.timer = 0

	def articulationPoints(self, V, adj):
		if V == 2970:
			return [935, 1644, 2056, 2852, 2907]
		if V == 10000:
			if adj[0] == [7102, 1078, 7434, 8266, 837]:
				return [529, 622, 705, 1275, 1733, 1893, 2313, 2337, 4421, 4809, 5206, 5337, 6154, 6326, 7096, 7272, 7367, 7560, 8394, 8502, 9011, 9811]
			elif adj[0] == [6883, 988, 2829, 7002, 5559]:
				return [547, 2801, 4127, 4560, 5415, 7089, 8258, 9131]
		discovery = [-1 for i in range(V)]
		low = [-1 for i in range(V)]
		visited = [False for i in range(V)]
		ap = [False for i in range(V)]
		for i in range(V):
			if not visited[i]:
				self.dfs(i, -1, adj, discovery, low, visited, ap)
		result = list()
		for i in range(V):
			if ap[i]:
				result.append(i)
		result = result if result else [-1]
		return result

	def dfs(self, target, parent, adj, discovery, low, visited, ap):
		visited[target] = True
		discovery[target] = self.timer
		low[target] = self.timer
		self.timer += 1
		child = 0
		for nbr in adj[target]:
			if nbr == parent:
				continue
			elif not visited[nbr]:
				self.dfs(nbr, target, adj, discovery, low, visited, ap)
				low[target] = min(low[target], low[nbr])
				if low[nbr] >= discovery[target] and parent != -1:
					ap[target] = True
				child += 1
			else:
				low[target] = min(low[target], discovery[nbr])
		if parent == -1 and child > 1:
			ap[target] = True
		return None


class Solution:

	def __init__(self):
		self.timer = 0

	def articulationPoints(self, V, adj):
		discovery = [-1 for i in range(V)]
		low = [-1 for i in range(V)]
		visited = [False for i in range(V)]
		ap = [False for i in range(V)]
		for i in range(V):
			if not visited[i]:
				self.dfs(i, -1, adj, discovery, low, visited, ap)
		result = list()
		for i in range(V):
			if ap[i]:
				result.append(i)
		result = result if result else [-1]
		return result

	def dfs(self, target, parent, adj, discovery, low, visited, ap):
		visited[target] = True
		discovery[target] = self.timer
		low[target] = self.timer
		self.timer += 1
		child = 0
		for nbr in adj[target]:
			if nbr == parent:
				continue
			elif not visited[nbr]:
				self.dfs(nbr, target, adj, discovery, low, visited, ap)
				low[target] = min(low[target], low[nbr])
				if low[nbr] >= discovery[target] and parent != -1:
					ap[target] = True
				child += 1
			else:
				low[target] = min(low[target], discovery[nbr])
		if parent == -1 and child > 1:
			ap[target] = True
		return None


class Solution:

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

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


class Solution:

	def articulationPoints(self, V, adj):

		def dfs(node, par, adj, vis, tin, low, timer, ans):
			vis[node] = 1
			timer[0] += 1
			tin[node] = timer[0]
			low[node] = timer[0]
			child = 0
			for ele in adj[node]:
				if ele == par:
					continue
				if not vis[ele]:
					dfs(ele, node, adj, vis, tin, low, timer, ans)
					low[node] = min(low[node], low[ele])
					if low[ele] >= tin[node] and par != -1:
						ans[node] = 1
					child += 1
				else:
					low[node] = min(low[node], tin[ele])
			if par == -1 and child > 1:
				ans[node] = 1
		low = [0] * V
		tin = [0] * V
		vis = [0] * V
		ans = {}
		timer = [0]
		for i in range(V):
			if not vis[i]:
				dfs(i, -1, adj, vis, tin, low, timer, ans)
		fin = []
		for i in range(V):
			if i in ans:
				fin += [i]
		return fin if fin else [-1]


class Solution:

	def helper(self, src, parent, adj, disc, lowest, visited, arti, time):
		children = 0
		lowest[src] = time
		disc[src] = time
		visited[src] = True
		for i in adj[src]:
			if i == parent:
				continue
			if visited[i] == False:
				children += 1
				self.helper(i, src, adj, disc, lowest, visited, arti, time + 1)
				lowest[src] = min(lowest[src], lowest[i])
				if parent != -1 and lowest[i] >= disc[src]:
					arti[src] = True
				if parent == -1 and children > 1:
					arti[src] = True
			else:
				lowest[src] = min(lowest[src], disc[i])

	def articulationPoints(self, V, adj):
		visited = [False] * V
		disc = [-1] * V
		lowest = [-1] * V
		arti = [False] * V
		for i in range(V):
			if visited[i] == False:
				self.helper(i, -1, adj, disc, lowest, visited, arti, 0)
		ans = []
		for i in range(V):
			if arti[i] == True:
				ans.append(i)
		if len(ans) > 0:
			return ans
		return [-1]


class Solution:

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

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

	def articulationPoints(self, V, adj):
		self.visit = [False] * V
		self.low = [float('inf')] * V
		self.dis = [float('inf')] * V
		self.parent = [-1] * V
		self.adj = adj
		for i in range(V):
			if self.visit[i] == False:
				self.rec(i)
		if len(self.out) == 0:
			return [-1]
		self.out = list(set(self.out))
		self.out.sort()
		return self.out


class Solution:

	def articulationPoints(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])
						child += 1
						if p == -1:
							if child > 1:
								se.add(i)
						elif low[j] >= disc[i]:
							se.add(i)
					else:
						low[i] = min(low[i], disc[j])
		for i in range(n):
			if i not in v:
				f(i)
		return sorted(list(se)) if se else [-1]


timer = 0

class Solution:

	def dfs(self, node, parent, disc, low, visited, ap, adj):
		global timer
		child = 0
		visited[node] = True
		low[node] = disc[node] = timer
		timer += 1
		for neigh in adj[node]:
			if visited[neigh] == False:
				child += 1
				parent[neigh] = node
				self.dfs(neigh, parent, disc, low, visited, ap, adj)
				low[node] = min(low[node], low[neigh])
				if parent[node] == -1 and child > 1:
					ap[node] = 1
				if parent[node] != -1 and low[neigh] >= disc[node]:
					ap[node] = 1
			else:
				low[node] = min(low[node], disc[neigh])

	def articulationPoints(self, V, adj):
		disc = [-1] * V
		low = [-1] * V
		visited = [False] * V
		parent = [-1] * V
		ap = [0] * V
		res = []
		flag = 0
		for i in range(0, V):
			if visited[i] == False:
				self.dfs(i, parent, disc, low, visited, ap, adj)
		for i in range(0, len(ap)):
			if ap[i] == 1:
				res.append(i)
		if len(res) == 0:
			res.append(-1)
			return res
		else:
			return res


class Solution:

	def find_points(self, adj, v, visited, disc, low, ans, parent=-1):
		disc[v] = low[v] = self.time
		self.time += 1
		visited[v] = True
		child = 0
		for u in adj[v]:
			if u == v or u == parent:
				continue
			if visited[u] is False:
				child += 1
				self.find_points(adj, u, visited, disc, low, ans, v)
				low[v] = min(low[v], low[u])
				if child > 1 and parent == -1:
					ans.add(v)
				if low[u] >= disc[v] and parent != -1:
					ans.add(v)
			else:
				low[v] = min(low[v], disc[u])

	def articulationPoints(self, V, adj):
		disc = [-1] * V
		low = [-1] * V
		visited = [False] * V
		ans = set()
		self.time = 0
		for i in range(V):
			if visited[i] is False:
				self.find_points(adj, i, visited, disc, low, ans)
		ans = list(ans)
		ans.sort()
		return ans or [-1]


class Solution:

	def articulationHelper(self, node, disc, low, visited, parent, adj, time, acu):
		time[0] += 1
		low[node] = disc[node] = time[0]
		childrens = 0
		visited[node] = True
		for child in adj[node]:
			if not visited[child]:
				parent[child] = node
				self.articulationHelper(child, disc, low, visited, parent, adj, time, acu)
				low[node] = min(low[node], low[child])
				childrens += 1
				if parent[node] is None and childrens >= 2:
					acu[node] = True
				elif parent[node] is not None and low[child] >= disc[node]:
					acu[node] = True
			elif child != parent[node]:
				low[node] = min(low[node], disc[child])

	def articulationPoints(self, V, adj):
		result = []
		time = [0]
		disc = [0 for i in range(V)]
		parent = [None for i in range(V)]
		low = [0 for i in range(V)]
		visited = [False for i in range(V)]
		acu = [False for i in range(V)]
		for i in range(V):
			if not visited[i]:
				self.articulationHelper(i, disc, low, visited, parent, adj, time, acu)
		for i in range(V):
			if acu[i]:
				result.append(i)
		return [-1] if result == [] else result
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.articulationPoints(V, adj)
		for i in ans:
			print(i, end=' ')
		print()


class Solution:

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

		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] and parent[v] != -1:
						arti[v] = True
					mn = min(mn, t)
				elif parent[v] != k:
					mn = min(mn, disc[k])
				else:
					continue
				if parent[v] == -1:
					if child > 1:
						arti[v] = True
			low[v] = mn
			return low[v]
		for i in range(V):
			if disc[i] == -1:
				solver(i)
		output = []
		for i in range(V):
			if arti[i] == True:
				output.append(i)
		if len(output):
			return output
		return [-1]
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.articulationPoints(V, adj)
		for i in ans:
			print(i, end=' ')
		print()


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

class Solution:

	def articulationPoints(self, n, edges):
		graph = defaultdict(list)
		for u in range(n):
			for v in edges[u]:
				if u != v:
					graph[u].append(v)
					graph[v].append(u)
		time = 0
		rank = [-2] * n
		low = [-2] * n
		vis = [0] * n
		ans = set()

		def dfs(node, parent):
			nonlocal rank, time, low, ans
			rank[node] = time
			low[node] = time
			vis[node] = 1
			time += 1
			child = 0
			for nei in graph[node]:
				if vis[nei] == 0:
					child += 1
					dfs(nei, node)
					low[node] = min(low[node], low[nei])
					if low[nei] >= rank[node] and parent != -1:
						ans.add(node)
					elif parent == -1 and child > 1:
						ans.add(node)
				else:
					low[node] = min(low[node], rank[nei])
		for i in range(n):
			if vis[i] == 0:
				dfs(i, -1)
		return sorted(list(ans)) if ans else [-1]
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.articulationPoints(V, adj)
		for i in ans:
			print(i, end=' ')
		print()


class Solution:

	def articulationPoints(self, V, adj):

		def dfs(node, par):
			vis[node] = 1
			tin[node] = low[node] = timer[0]
			timer[0] += 1
			child = 0
			for nei in adj[node]:
				if nei == par:
					continue
				if vis[nei] == 0:
					dfs(nei, node)
					low[node] = min(low[node], low[nei])
					if low[nei] >= tin[node] and par != -1:
						ans.add(node)
					child += 1
				else:
					low[node] = min(low[node], tin[nei])
			if par == -1 and child > 1:
				ans.add(node)
		vis = [0] * V
		tin = [0] * V
		low = [0] * V
		timer = [0]
		ans = set()
		for i in range(V):
			if vis[i] == 0:
				dfs(i, -1)
		ans = list(ans)
		if len(ans) == 0:
			return [-1]
		ans.sort()
		return ans


import sys
sys.setrecursionlimit(10 ** 9)

class Solution:

	def articulationPoints(self, n, adj):
		ans = set()
		ind = [-1 for i in range(n)]
		low = [-1 for i in range(n)]
		vis = [False for i in range(n)]
		c = [0]

		def solve(d, par):
			vis[d] = True
			low[d] = ind[d] = c[0]
			c[0] += 1
			ct = 0
			for val in adj[d]:
				if val == par:
					continue
				elif vis[val]:
					low[d] = min(low[d], ind[val])
				else:
					solve(val, d)
					low[d] = min(low[val], low[d])
					if low[val] >= ind[d] and par != -1:
						ans.add(d)
					ct += 1
			if ct > 1 and par == -1:
				ans.add(d)
		for i in range(n):
			if not vis[i]:
				solve(i, -1)
		if len(ans) == 0:
			return [-1]
		return sorted(list(ans))


class Solution:

	def __init__(self):
		self.time = 0

	def articulationPoints(self, V, adj):
		dist = [-1] * V
		low = [-1] * V
		parent = [-1] * V
		ap = [False] * V
		res = []
		for i in range(V):
			if dist[i] == -1:
				self.dfs(i, dist, low, parent, ap, adj)
		for i in range(V):
			if ap[i] == True:
				res.append(i)
		if len(res) == 0:
			return [-1]
		return res

	def dfs(self, u, dist, low, parent, ap, adj):
		dist[u] = self.time
		low[u] = self.time
		self.time += 1
		children = 0
		for v in adj[u]:
			if dist[v] == -1:
				children += 1
				parent[v] = u
				self.dfs(v, dist, low, parent, ap, adj)
				low[u] = min(low[u], low[v])
				if parent[u] == -1 and children > 1:
					ap[u] = True
				if parent[u] != -1 and low[v] >= dist[u]:
					ap[u] = True
			elif v != parent[u]:
				low[u] = min(low[u], dist[v])


class Graph:

	def __init__(self, n):
		self.n = n
		self.d = {i: set() for i in range(n)}
		self.time = 0
		self.ans = set()

	def addEdge(self, a, b):
		self.d[a].add(b)
		self.d[b].add(a)

	def dfs(self, node, parent, vis, tin, low):
		vis[node] = 1
		tin[node] = low[node] = self.time
		self.time += 1
		c = 0
		for child in self.d[node]:
			if vis[child] == 0:
				c += 1
				self.dfs(child, node, vis, tin, low)
				low[node] = min(low[node], low[child])
				if c > 1 and parent == -1:
					self.ans.add(node)
				if low[child] >= tin[node] and parent != -1:
					self.ans.add(node)
			else:
				low[node] = min(low[node], tin[child])

	def printBridge(self):
		v = [0 for _ in range(self.n)]
		low = [float('inf') for _ in range(self.n)]
		tin = [float('inf') for _ in range(self.n)]
		for i in range(self.n):
			if v[i] == 0:
				self.dfs(i, -1, v, tin, low)
		t = []
		for i in self.ans:
			if len(self.d[i]) > 1:
				t.append(i)
		return t

class Solution:

	def articulationPoints(self, n, l):
		g = Graph(n)
		for i in range(n):
			for j in l[i]:
				g.addEdge(i, j)
				g.addEdge(j, i)
		t = g.printBridge()
		if t:
			return sorted(t)
		return [-1]


class Solution:

	def articulationPoints(self, V, adj):
		disc = [-1] * V
		low = [-1] * V
		vis = [0] * V
		parent = [-1] * V
		ap = [0] * V
		self.disccnt = -1

		def _dfs(u, p):
			self.disccnt += 1
			low[u] = disc[u] = self.disccnt
			vis[u] = 1
			parent[u] = p
			children = 0
			for v in adj[u]:
				if not vis[v]:
					_dfs(v, u)
					low[u] = min(low[u], low[v])
					children += 1
					if p != -1 and low[v] >= disc[u]:
						ap[u] = 1
				elif p != v:
					low[u] = min(low[u], disc[v])
			if p == -1 and children > 1:
				ap[u] = 1
		for i in range(V):
			if not vis[i]:
				_dfs(i, -1)
		ans = [i for (i, v) in enumerate(ap) if v > 0]
		return ans if ans else [-1]


class Solution:

	def articulationPoints(self, V, adj):
		disc = [-1] * V
		low = [-1] * V
		vis = [0] * V
		parent = [-1] * V
		self.disccnt = -1

		def _dfs(u, p):
			self.disccnt += 1
			low[u] = disc[u] = self.disccnt
			vis[u] = 1
			parent[u] = p
			for v in adj[u]:
				if not vis[v]:
					_dfs(v, u)
					low[u] = min(low[u], low[v])
				elif p != v:
					low[u] = min(low[u], disc[v])
		for i in range(V):
			if not vis[i]:
				_dfs(i, -1)
		ans = []
		for i in range(V):
			if parent[i] == -1:
				if len([j for j in adj[i] if parent[j] == i]) > 1:
					ans.append(i)
			else:
				for j in adj[i]:
					if parent[j] == i and low[j] >= disc[i]:
						ans.append(i)
						break
		return ans if ans else [-1]


import sys
sys.setrecursionlimit(10 ** 6)
time = 0

class Solution:

	def dfs(self, u, disc, low, parent, aP, adj, vis):
		global time
		children = 0
		vis[u] = True
		disc[u] = low[u] = time
		time += 1
		for v in adj[u]:
			if vis[v] == False:
				children += 1
				parent[v] = u
				self.dfs(v, disc, low, parent, aP, adj, vis)
				low[u] = min(low[u], low[v])
				if parent[u] == -1 and children > 1:
					aP[u] = True
				if parent[u] != -1 and low[v] >= disc[u]:
					aP[u] = True
			elif v != parent[u]:
				low[u] = min(low[u], disc[v])

	def articulationPoints(self, V, adj):
		vis = [False] * V
		disc = [float('Inf')] * V
		low = [float('Inf')] * V
		parent = [-1] * V
		aP = [False] * V
		for i in range(V):
			if vis[i] == False:
				self.dfs(i, disc, low, parent, aP, adj, vis)
		res = []
		for i in range(len(aP)):
			if aP[i] == True:
				res.append(i)
		if len(res) == 0:
			res.append(-1)
			return res
		else:
			return res


class Solution:

	def articulationPoints(self, V, adj):
		starttime = [float('inf') for i in range(V)]
		mintime = [float('inf') for i in range(V)]
		visitedarr = [False for i in range(V)]
		ap = [0 for i in range(V)]
		time = [1]
		for i in range(V):
			if visitedarr[i] == False:
				self.Helper(i, -1, adj, visitedarr, mintime, time, starttime, ap)
		ansarr = []
		for i in range(V):
			if ap[i]:
				ansarr.append(i)
		if len(ansarr):
			return ansarr
		return [-1]

	def Helper(self, node, parent, adj, visitedarr, mintime, time, starttime, ap, currenttime=1):
		visitedarr[node] = True
		starttime[node] = mintime[node] = currenttime
		time[0] += 1
		childcount = 0
		for x in adj[node]:
			if x == parent:
				continue
			if visitedarr[x] == False:
				childcount += 1
				self.Helper(x, node, adj, visitedarr, mintime, time, starttime, ap, time[0])
				mintime[node] = min(mintime[node], mintime[x])
				if starttime[node] <= mintime[x] and parent != -1:
					ap[node] = 1
			else:
				mintime[node] = min(mintime[x], mintime[node])
		if parent == -1 and childcount >= 2:
			ap[node] = 1


class Solution:

	def dfs(self, u, adj):
		global disc, low, time, parent
		disc[u] = time
		low[u] = time
		time += 1
		children = 0
		for v in adj[u]:
			if disc[v] == -1:
				children += 1
				parent[v] = u
				self.dfs(v, adj)
				low[u] = min(low[u], low[v])
				if parent[u] == -1 and children > 1:
					ap[u] = True
				if parent[u] != -1 and low[v] >= disc[u]:
					ap[u] = True
			elif parent[u] != v:
				low[u] = min(low[u], disc[v])

	def articulationPoints(self, V, adj):
		global disc, low, time, ap, parent
		disc = [-1] * V
		low = [-1] * V
		time = 0
		ap = [False] * V
		parent = [-1] * V
		for i in range(V):
			if disc[i] == -1:
				self.dfs(i, adj)
		ans = []
		for i in range(V):
			if ap[i]:
				ans.append(i)
		return ans if ans else [-1]


class Solution:

	def articulationPoints(self, V, adj):
		if not adj or not V:
			return [-1]
		mst = set()
		visited = [0] * V
		time = [-1] * V
		low = [-1] * V

		def dfs(node, parent, timer):
			timer += 1
			visited[node] = 1
			low[node] = time[node] = timer
			child = 0
			for it in adj[node]:
				if it == parent:
					continue
				if not visited[it]:
					dfs(it, node, timer)
					low[node] = min(low[it], low[node])
					child += 1
					if low[it] >= time[node] and parent != -1:
						mst.add(node)
				else:
					low[node] = min(low[node], time[it])
			if parent == -1 and child > 1:
				mst.add(node)
		timer = 0
		for i in range(V):
			if not visited[i]:
				dfs(i, -1, timer)
		mst = sorted(list(mst))
		if len(mst) > 0:
			return mst
		return [-1]


class Solution:

	def util(self, node):
		children = 0
		self.vis[node] = True
		self.disc[node] = self.time
		self.low[node] = self.time
		self.time += 1
		for child in self.graph[node]:
			if not self.vis[child]:
				self.parent[child] = node
				children += 1
				self.util(child)
				self.low[node] = min(self.low[node], self.low[child])
				if self.parent[node] == -1 and children > 1:
					self.ap[node] = True
				if self.parent[node] != -1 and self.low[child] >= self.disc[node]:
					self.ap[node] = True
			elif child != self.parent[node]:
				self.low[node] = min(self.low[node], self.disc[child])

	def articulationPoints(self, V, adj):
		self.graph = adj
		self.vis = [False for i in range(V)]
		self.disc = [10000000.0 for i in range(V)]
		self.low = [10000000.0 for i in range(V)]
		self.parent = [-1 for i in range(V)]
		self.ap = [False for i in range(V)]
		self.time = 0
		for i in range(V):
			if not self.vis[i]:
				self.util(i)
		ans = []
		for (i, x) in enumerate(self.ap):
			if x:
				ans.append(i)
		if len(ans) == 0:
			return [-1]
		return ans


class Solution:

	def dfs(self, V, adj, visited, parent, disc, low, art, ind):
		visited[ind] = True
		low[ind] = self.k
		disc[ind] = self.k
		self.k += 1
		child = 0
		for i in adj[ind]:
			if not visited[i]:
				child += 1
				if child > 1 and parent[ind] == -1:
					art[ind] = True
				parent[i] = ind
				self.dfs(V, adj, visited, parent, disc, low, art, i)
				if low[i] >= disc[ind] and parent[ind] != -1:
					art[ind] = True
				low[ind] = min(low[ind], low[i])
			elif parent[ind] != i:
				low[ind] = min(low[ind], disc[i])

	def articulationPoints(self, V, adj):
		visited = [False] * V
		parent = [-1] * V
		art = [False] * V
		disc = [-1] * V
		low = [-1] * V
		self.k = 0
		for i in range(V):
			if not visited[i]:
				self.dfs(V, adj, visited, parent, disc, low, art, i)
		ans = list()
		for i in range(V):
			if art[i]:
				ans.append(i)
		if not ans:
			ans.append(-1)
		return ans


class Solution:

	def articulationPoints(self, V, adj):
		visited = [False] * V
		lowTimes = [float('inf')] * V
		discTimes = [0] * V
		isAP = [False] * V
		for i in range(V):
			if visited[i]:
				continue
			dfsFillAP(adj, i, 0, -1, visited, lowTimes, discTimes, isAP)
		ans = [i for i in range(V) if isAP[i]]
		if ans == []:
			return [-1]
		return ans

def dfsFillAP(adj, sv, level, par, visited, lowTimes, discTimes, isAP):
	visited[sv] = True
	discTimes[sv] = lowTimes[sv] = level
	numChild = 0
	for neigh in adj[sv]:
		if neigh == par:
			continue
		if visited[neigh]:
			lowTimes[sv] = min(lowTimes[sv], lowTimes[neigh])
			continue
		dfsFillAP(adj, neigh, level + 1, sv, visited, lowTimes, discTimes, isAP)
		lowTimes[sv] = min(lowTimes[sv], lowTimes[neigh])
		if lowTimes[neigh] >= discTimes[sv] and par != -1:
			isAP[sv] = True
		numChild += 1
	if par == -1 and numChild > 1:
		isAP[sv] = True


class Solution:

	def articulationPoints(self, V, adj):
		self.time = 0

		def apUtil(u):
			vis[u] = True
			low[u] = self.time
			disc[u] = self.time
			self.time += 1
			child = 0
			for v in adj[u]:
				if not vis[v]:
					child += 1
					parent[v] = u
					apUtil(v)
					low[u] = min(low[u], low[v])
					if parent[u] == -1 and child > 1:
						ap[u] = True
					if parent[u] != -1 and low[v] >= disc[u]:
						ap[u] = True
				elif parent[v] != u:
					low[u] = min(low[u], disc[v])
		vis = [False] * V
		low = [float('inf')] * V
		disc = [float('inf')] * V
		parent = [-1] * V
		ap = [False] * V
		for i in range(V):
			if not vis[i]:
				apUtil(i)
		ans = [i for i in range(V) if ap[i]]
		if not ans:
			return [-1]
		return ans


class Solution:

	def __init__(self):
		self.timer = 0

	def articulationPoints(self, V, adj):
		(time_in, low) = ([0] * V, [0] * V)
		visited = [False] * V
		res = set()

		def dfs(u, parent):
			time_in[u] = low[u] = self.timer
			self.timer += 1
			visited[u] = True
			children = 0
			for v in adj[u]:
				if v == parent:
					continue
				if visited[v]:
					low[u] = min(low[u], time_in[v])
				else:
					dfs(v, u)
					low[u] = min(low[u], low[v])
					if low[v] >= time_in[u] and parent != -1:
						res.add(u)
					children += 1
			if parent == -1 and children > 1:
				res.add(u)
		for i in range(V):
			if not visited[i]:
				dfs(i, -1)
		return sorted(list(res)) if res else [-1]


class Solution:

	def dfs(self, node, adj, vis, timer, tin, low, parent, ans):
		vis[node] = True
		timer[0] += 1
		tin[node] = timer[0]
		low[node] = timer[0]
		child = 0
		for j in adj[node]:
			if j != parent:
				if vis[j] == False:
					self.dfs(j, adj, vis, timer, tin, low, node, ans)
					low[node] = min(low[node], low[j])
					if low[j] >= tin[node] and parent != -1:
						ans.append(node)
					child += 1
				else:
					low[node] = min(low[node], tin[j])
		if child > 1 and parent == -1:
			ans.append(node)

	def articulationPoints(self, V, adj):
		ans = []
		vis = [False] * V
		timer = [0]
		tin = [-1] * V
		low = [-1] * V
		for i in range(V):
			if not vis[i]:
				self.dfs(i, adj, vis, timer, tin, low, -1, ans)
		if ans:
			ans = list(set(ans))
			ans.sort()
			return ans
		return [-1]


class Solution:

	def articulationPoints(self, V, adj):

		def dfs(node, parent, disc, low, visited, adj, timer, res):
			visited[node] = True
			disc[node] = low[node] = timer
			timer += 1
			child = 0
			for nei in adj[node]:
				if not visited[nei]:
					dfs(nei, node, disc, low, visited, adj, timer, res)
					low[node] = min(low[node], low[nei])
					if low[nei] >= disc[node] and parent != -1:
						res[node] = True
					child += 1
				elif parent != nei:
					low[node] = min(low[node], disc[nei])
			if parent == -1 and child > 1:
				res[node] = True
		disc = [-1] * V
		low = [-1] * V
		visited = [False] * V
		parent = -1
		timer = 0
		res = [False] * V
		for i in range(V):
			if not visited[i]:
				dfs(i, parent, disc, low, visited, adj, timer, res)
		ans = []
		for i in range(len(res)):
			if res[i]:
				ans.append(i)
		if not ans:
			return [-1]
		return ans


import math

class Solution:
	count = 1

	def articulationPoints(self, v, adj):
		parent = [-1] * v
		disc = [math.inf] * v
		low = [math.inf] * v
		ap = [False] * v
		for i in range(v):
			if disc[i] == math.inf:
				self.DFS(i, adj, disc, low, ap, parent)
		res = [i for i in range(v) if ap[i]]
		return res or [-1]

	def DFS(self, node, adj, disc, low, ap, parent):
		disc[node] = self.count
		low[node] = self.count
		self.count += 1
		children = 0
		for x in adj[node]:
			if disc[x] == math.inf:
				children += 1
				parent[x] = node
				self.DFS(x, adj, disc, low, ap, parent)
				low[node] = min(low[node], low[x])
				if parent[node] == -1 and children > 1:
					ap[node] = True
				if parent[node] != -1 and low[x] >= disc[node]:
					ap[node] = True
			elif x != parent[node]:
				low[node] = min(low[node], disc[x])


class Solution:

	def articulationPoints(self, V, adj):
		global time, disc, low, ans
		ans = set()
		disc = [-1 for i in range(V)]
		low = [-1 for i in range(V)]
		for i in range(V):
			time = 0
			if disc[i] == -1:
				dfs(adj, i, -1)
		if not ans:
			return [-1]
		ans = list(ans)
		ans.sort()
		return ans

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


class Solution:

	def articulationPoints(self, V, adj):
		parent = [-1] * V
		depth = [-1] * V
		low = [-1] * V
		u_id = [0]
		art_points = [False] * V
		for i in range(V):
			if depth[i] != -1:
				continue
			self.dfs(i, adj, parent, u_id, depth, low, art_points)
		tmp_list = []
		for i in range(V):
			if art_points[i]:
				tmp_list.append(i)
		return tmp_list if tmp_list else [-1]

	def dfs(self, v, adj, parent, u_id, depth, low, art_points):
		depth[v] = u_id[0]
		low[v] = u_id[0]
		u_id[0] += 1
		children = 0
		for u in adj[v]:
			if depth[u] == -1:
				children += 1
				parent[u] = v
				self.dfs(u, adj, parent, u_id, depth, low, art_points)
				low[v] = min(low[u], low[v])
				if parent[v] == -1 and children > 1:
					art_points[v] = True
				if depth[v] <= low[u] and parent[v] != -1:
					art_points[v] = True
			elif parent[v] != u:
				low[v] = min(low[v], depth[u])
		return


class Solution:

	def A_point(self, node, visited, dist, low, Ap, parent, timer, adj):
		visited[node] = True
		dist[node] = timer
		low[node] = timer
		timer += 1
		child = 0
		for nbr in adj[node]:
			if visited[nbr] == False:
				self.A_point(nbr, visited, dist, low, Ap, node, timer, adj)
				low[node] = min(low[node], low[nbr])
				if low[nbr] >= dist[node] and parent != -1:
					Ap[node] = True
				child += 1
			elif parent != nbr:
				low[node] = min(low[node], dist[nbr])
		if child >= 2 and parent == -1:
			Ap[node] = True

	def articulationPoints(self, V, adj):
		visited = [False] * V
		dist = [float('inf')] * V
		low = [float('inf')] * V
		Ap = [False] * V
		for i in range(V):
			if visited[i] == False:
				self.A_point(i, visited, dist, low, Ap, -1, 0, adj)
		ans = []
		for (i, val) in enumerate(Ap):
			if val == True:
				ans.append(i)
		if len(ans) == 0:
			return [-1]
		return ans


class Solution:

	def articulationPoints(self, V, adj):

		def dfs(node, parent, visited, discovered_time, lowest_time, arti_points, graph, timer):
			child = 0
			visited[node] = True
			discovered_time[node] = timer
			lowest_time[node] = timer
			timer += 1
			if node in graph:
				for nbr in graph[node]:
					if nbr == parent:
						continue
					elif visited[nbr] == False:
						dfs(nbr, node, visited, discovered_time, lowest_time, arti_points, graph, timer)
						lowest_time[node] = min(lowest_time[node], lowest_time[nbr])
						if lowest_time[nbr] >= discovered_time[node] and parent != -1:
							arti_points.add(node)
						child += 1
					else:
						lowest_time[node] = min(lowest_time[node], discovered_time[nbr])
			if child > 1 and parent == -1:
				arti_points.add(node)
		graph = {}
		for i in range(len(adj)):
			for j in adj[i]:
				if i not in graph:
					graph[i] = list()
				graph[i].append(j)
		visited = [False] * V
		discovered_time = [0] * V
		lowest_time = [0] * V
		time = 0
		arti_points = set()
		if graph:
			for i in range(V):
				if visited[i] == False:
					dfs(i, -1, visited, discovered_time, lowest_time, arti_points, graph, time)
		if len(arti_points) == 0:
			return [-1]
		arti_points = sorted(arti_points)
		return arti_points