Given a Directed Graph, find a Mother Vertex in the Graph (if present). 
A Mother Vertex is a vertex through which we can reach all the other vertices of the Graph.
 
Example 1:
Input: 
Output: 0
Explanation: According to the given edges, all 
nodes can be reaced from nodes from 0, 1 and 2. 
But, since 0 is minimum among 0,1 and 2, so 0 
is the output.
Example 2:
Input: 
Output: -1
Explanation: According to the given edges, 
no vertices are there from where we can 
reach all vertices. So, output is -1.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function findMotherVertex() which takes V denoting the number of vertices and adjacency list as imput parameter and returns the verticex from through which we can traverse all other vertices of the graph. If there is more than one possible nodes then returns the node with minimum value.If not possible returns -1.
 
Expected Time Complexity: O(V + E)
Expected Space Compelxity: O(V)
 
Constraints:
1 ≤ V ≤ 500

Source: geeksforgeeks | Difficulty: EASY
Tags: Graph algorithms

Data structures

Graph traversal

Starter code: 

class Solution:

    

    #Function to find a Mother Vertex in the Graph.

	def findMotherVertex(self, V, adj):

		#Code here

Solutions:
from collections import *

class Solution:

	def findMotherVertex(self, V, adj):
		stack = deque([])
		vis = [False] * V

		def fillstack(cur):
			vis[cur] = True
			for adja in adj[cur]:
				if not vis[adja]:
					fillstack(adja)
			stack.append(cur)
		for i in range(V):
			if not vis[i]:
				fillstack(i)
		vis = [False] * V

		def dfs(cur):
			vis[cur] = True
			for adja in adj[cur]:
				if not vis[adja]:
					dfs(adja)
		probablemother = stack.pop()
		dfs(probablemother)
		if sum(vis) == V:
			return probablemother
		return -1
		return -1


class Solution:

	def findMotherVertex(self, V, adj):
		stack = []
		visited = set()
		count = {'val': 0}

		def dfs(u):
			if u in visited:
				return
			visited.add(u)
			for v in adj[u]:
				dfs(v)
			stack.append(u)
			count['val'] += 1
		for i in range(V):
			if i not in visited:
				dfs(i)
		mother_vertex = stack[-1]
		count['val'] = 0
		visited = set()
		dfs(mother_vertex)
		return mother_vertex if count['val'] == V else -1


class Solution:

	def DFSUtil(self, adj, v, visited):
		visited[v] = True
		for i in adj[v]:
			if visited[i] == False:
				self.DFSUtil(adj, i, visited)

	def findMotherVertex(self, V, adj):
		visited = [False] * V
		v = 0
		for i in range(V):
			if visited[i] == False:
				self.DFSUtil(adj, i, visited)
				v = i
		visited = [False] * V
		self.DFSUtil(adj, v, visited)
		if any((i == False for i in visited)):
			return -1
		else:
			return v


class Solution:

	def dfs(self, node, adj, vis):
		vis[node] = 1
		ans = 1
		for i in adj[node]:
			if vis[i] == 0:
				ans += self.dfs(i, adj, vis)
		return ans

	def topo(self, node, st, adj, vis):
		vis[node] = 1
		for i in adj[node]:
			if vis[i] == 0:
				self.topo(i, st, adj, vis)
		st.append(node)

	def findMotherVertex(self, V, adj):
		st = []
		vis = [0] * V
		for i in range(V):
			if vis[i] == 0:
				self.topo(i, st, adj, vis)
		vis = [0] * V
		last_visited_node = st.pop()
		count = self.dfs(last_visited_node, adj, vis)
		if count == V:
			return last_visited_node
		else:
			return -1


class Solution:

	def findMotherVertex(self, V, adj):
		g2 = dict()
		for i in range(V):
			g2[i] = True
		l = []

		def dfs(g1, g2, s):
			g2[s] = False
			y = 1
			for i in g1[s]:
				if g2[i]:
					y = y + dfs(g1, g2, i)
			return y

		def topo(g1, g2, s):
			g2[s] = False
			for i in g1[s]:
				if g2[i]:
					topo(g1, g2, i)
			l.append(s)
		for i in range(V):
			if g2[i] == False:
				continue
			topo(adj, g2, i)
		for i in range(V):
			g2[i] = True
		x = l.pop()
		count = dfs(adj, g2, x)
		if count == V:
			return x
		return -1


class Solution:

	def findMotherVertex(self, V, adj):
		li = []
		visited = [False for i in range(V)]
		for i in range(V):
			if visited[i] == 0:
				self.topo(i, li, adj, visited)
		visited = [False] * V
		last_visited = li.pop()
		count = self.dfs(last_visited, adj, visited)
		if count == V:
			return last_visited
		else:
			return -1

	def dfs(self, node, adj, visited):
		visited[node] = 1
		ans = 1
		for i in adj[node]:
			if visited[i] == 0:
				ans += self.dfs(i, adj, visited)
		return ans

	def topo(self, node, li, adj, visited):
		visited[node] = 1
		for i in adj[node]:
			if visited[i] == 0:
				self.topo(i, li, adj, visited)
		li.append(node)


class Solution:

	def findMotherVertex(self, V, adj):
		visited = [False] * V
		mother_vertex = None
		for v in range(V):
			if not visited[v]:
				self.dfs(v, visited, adj)
				mother_vertex = v
		visited = [False] * V
		self.dfs(mother_vertex, visited, adj)
		if False in visited:
			mother_vertex = -1
		return mother_vertex

	def dfs(self, source, visited, graph):
		visited[source] = True
		for edge in graph[source]:
			if not visited[edge]:
				self.dfs(edge, visited, graph)


class Solution:

	def dfsUtil(self, src, visited, adj):
		visited[src] = True
		for v in adj[src]:
			if not visited[v]:
				self.dfsUtil(v, visited, adj)

	def findMotherVertex(self, V, adj):
		visited = [False] * V
		last = -1
		for i in range(V):
			if not visited[i]:
				self.dfsUtil(i, visited, adj)
				last = i
		visited = [False] * V
		self.dfsUtil(last, visited, adj)
		if all(visited):
			return last
		else:
			return -1


class Solution:

	def dfs(self, adj, v):
		self.visited[v] = True
		for i in adj[v]:
			if not self.visited[i]:
				self.dfs(adj, i)

	def findMotherVertex(self, V, adj):
		self.visited = [False] * V
		last_vertex = 0
		for i in range(V):
			if not self.visited[i]:
				self.dfs(adj, i)
				last_vertex = i
		self.visited = [False] * V
		self.dfs(adj, last_vertex)
		if False not in self.visited:
			return last_vertex
		return -1


class Solution:

	def dfs(self, v, adj, visited):
		visited[v] = True
		for u in adj[v]:
			if visited[u] == False:
				self.dfs(u, adj, visited)
		return visited

	def findMotherVertex(self, V, adj):
		visited = [False] * len(adj)
		v = 0
		for i in range(len(adj)):
			if visited[i] == False:
				self.dfs(i, adj, visited)
				v = i
		visited = [False] * len(adj)
		self.dfs(v, adj, visited)
		if any((i == False for i in visited)):
			return -1
		else:
			return v


class Solution:

	def findMotherVertex(self, V, G):

		def dfsVisit(flag, G, s, q, visited):
			visited[s] = True
			if not flag:
				q[0][s] = q[1]
			for el in G[s]:
				if not visited[el]:
					if not flag:
						q[0][el] = q[1]
						dfsVisit(False, G, el, q, visited)
					else:
						dfsVisit(True, G, el, q, visited)
			if flag:
				q.append(s)

		def SCC(G):
			visited = [False for _ in range(len(G))]
			result = []
			for idx in range(len(G)):
				if not visited[idx]:
					dfsVisit(True, G, idx, result, visited)
			S = [[] for _ in range(len(G))]
			for i in range(len(G)):
				for a in G[i]:
					S[a].append(i)
			visited = [False for _ in range(len(G))]
			help = [_ for _ in range(len(G))]
			i = -1
			result = result[::-1]
			for el in result:
				if not visited[el]:
					i += 1
					dfsVisit(False, S, el, (help, i), visited)
			M = [[] for _ in range(i + 1)]
			is_connected = [[False for _ in range(len(G))] for _ in range(len(G))]
			for idx in range(len(G)):
				for el in G[idx]:
					if help[idx] != help[el] and (not is_connected[help[idx]][help[el]]):
						M[help[idx]].append(help[el])
						is_connected[help[idx]][help[el]] = True
			return (M, help)

		def TS(G):
			visited = [False for _ in range(len(G))]
			result = []
			for idx in range(len(G)):
				if not visited[idx]:
					dfsVisit(True, G, idx, result, visited)
			result = result[::-1]
			return result
		(M, help) = SCC(G)
		a = TS(M)[0]
		i = 0
		result = []
		visited = [False for _ in range(len(G))]
		while i < len(G):
			if help[i] == a:
				break
			i += 1
		dfsVisit(True, G, i, result, visited)
		if len(result) == len(G):
			return i
		return -1


from collections import deque

class Solution:

	def findMotherVertex(self, V, adj):

		def solve(s, visited, adj, count):
			ans = 1
			visited[s] = 1
			for i in adj[s]:
				if not i in visited:
					ans += solve(i, visited, adj, count)
			count[s] = ans
			return ans

		def dfs(s, visited, adj, stack):
			visited[s] = 1
			for i in adj[s]:
				if not i in visited:
					dfs(i, visited, adj, stack)
			stack += [s]
		visited = {}
		stack = []
		for i in range(V):
			if not i in visited:
				dfs(i, visited, adj, stack)
		count = [0] * V
		visited = {}
		solve(stack[-1], visited, adj, count)
		for i in range(V):
			if count[i] == V:
				return i
		return -1


class Solution:

	def dfs(self, node, visited, adj):
		visited[node] = 1
		for it in adj[node]:
			if visited[it] == 0:
				self.dfs(it, visited, adj)

	def findMotherVertex(self, V, adj):
		visited = [0] * V
		node = 0
		for i in range(V):
			if visited[i] == 0:
				self.dfs(i, visited, adj)
				node = i
		visited = [0] * V
		self.dfs(node, visited, adj)
		if any((i == 0 for i in visited)):
			return -1
		else:
			return node


from collections import deque

class Solution:

	def dfs(self, V, adj, visited):
		st = deque()
		st.append(V)
		visited[V] = 1
		while st:
			nd = st.pop()
			for ch in adj[nd]:
				if visited[ch] == 0:
					st.append(ch)
					visited[ch] = 1

	def findMotherVertex(self, V, adj):
		mother = 0
		visited = [0] * V
		for i in range(V):
			if visited[i] == 0:
				self.dfs(i, adj, visited)
				mother = i
		visited = [0] * V
		self.dfs(mother, adj, visited)
		for i in visited:
			if i != 1:
				return -1
		return mother


class Solution:

	def findMotherVertex(self, V, adj):
		visited = [False for _ in range(V)]
		v = 0
		for i in range(V):
			if not visited[i]:
				self.dfs(adj, visited, i)
				v = i
		visited = [False for _ in range(V)]
		self.dfs(adj, visited, v)
		if any((i == False for i in visited)):
			return -1
		return v

	def dfs(self, graph, visited, src):
		visited[src] = True
		for adj in graph[src]:
			if not visited[adj]:
				self.dfs(graph, visited, adj)


class Solution:

	def findMotherVertex(self, V, adj):
		visited = [False] * V
		v = 0
		for i in range(V):
			if not visited[i]:
				self.dfs(i, visited, adj)
				v = i
		visited = [False] * V
		self.dfs(v, visited, adj)
		if any((i == False for i in visited)):
			return -1
		else:
			return v

	def dfs(self, v, visited, adj):
		visited[v] = True
		for node in adj[v]:
			if not visited[node]:
				self.dfs(node, visited, adj)


class Solution:

	def dfs(self, pre, adj, visited):
		if pre not in visited:
			visited.add(pre)
			self.visit.add(pre)
			for i in adj[pre]:
				if i not in visited:
					self.dfs(i, adj, visited)

	def findMotherVertex(self, V, adj):
		self.visit = set()
		for i in range(V):
			visited = set()
			if i not in self.visit:
				self.dfs(i, adj, visited)
				if len(visited) == V:
					return i
		return -1


class Solution:

	def findMotherVertex(self, V, adj):
		s = set()

		def dfs(n):
			if n not in v:
				v.add(n)
				s.add(n)
			for i in adj[n]:
				if i not in v:
					dfs(i)
		for i in range(V):
			v = set()
			if i not in s:
				dfs(i)
				if len(v) == V:
					return i
			v = set()
		return -1


class Solution:

	def findMotherVertex(self, V, adj):
		visited = [False for i in range(V)]
		for i in range(V):
			if not visited[i]:
				ans = i
				self.dfs(i, adj, visited)
		visited = [False for i in range(V)]
		self.dfs(ans, adj, visited)
		for i in visited:
			if not i:
				return -1
		return ans

	def dfs(self, node, adj, visited):
		if not visited[node]:
			visited[node] = True
			for i in adj[node]:
				if not visited[i]:
					flag = True
					self.dfs(i, adj, visited)


def dfs(graph, visited, v, stack):
	visited[v] = True
	for i in graph[v]:
		if not visited[i]:
			dfs(graph, visited, i, stack)
	stack = stack.append(v)

class Solution:

	def findMotherVertex(self, V, adj):
		visited = [False] * V
		stack = []
		for i in range(V):
			if visited[i] == False:
				dfs(adj, visited, i, stack)
		visited = [False] * V
		dfs(adj, visited, stack[-1], [])
		if any((i == False for i in visited)):
			return -1
		return stack[-1]


class Solution:

	def findMotherVertex(self, V, adj):
		stack = []

		def dfs(graph, src, visited):
			nonlocal stack
			visited.add(src)
			for neighbor in graph[src]:
				if neighbor not in visited:
					dfs(graph, neighbor, visited)
			stack.append(src)
		visited = set()
		for i in range(V):
			if i not in visited:
				dfs(adj, i, visited)
		check = stack[-1]
		visited = set()
		dfs(adj, check, visited)
		if len(visited) == V:
			return check
		else:
			return -1


from queue import Queue

class Solution:

	def findMotherVertex(self, V, adj):

		def dfs(node, visited):
			visited[node] = 1
			for nbr in adj[node]:
				if visited[nbr] == -1:
					dfs(nbr, visited)
		visited = [-1] * V
		for node in range(V):
			if visited[node] == -1:
				dfs(node, visited)
				last = node
		visited = [-1] * V
		dfs(last, visited)
		if any((i == -1 for i in visited)):
			return -1
		else:
			return last


class Solution:

	def DFS(self, start, adj, visited):
		visited[start] = True
		for neighbour in adj[start]:
			if visited[neighbour] == False:
				self.DFS(neighbour, adj, visited)

	def findMotherVertex(self, v, adj):
		visited = [False for i in range(v)]
		possible_mother_vertex = []
		for i in range(v):
			if visited[i] == False:
				possible_mother_vertex.append(i)
				self.DFS(i, adj, visited)
		if len(possible_mother_vertex) == 1:
			return possible_mother_vertex[0]
		visited2 = [False for i in range(v)]
		start2 = possible_mother_vertex[-1]
		self.DFS(start2, adj, visited2)
		for visit in visited2:
			if visit == False:
				return -1
		return True


from collections import deque

class Solution:

	def findMotherVertex(self, V, adj):
		queue = deque()
		visitedCount = 0
		for i in range(V):
			visited = [False] * V
			queue.append(i)
			visited[i] = True
			visitedCount = 1
			while queue:
				if visitedCount == V:
					return i
				else:
					x = queue.popleft()
					for j in adj[x]:
						if not visited[j]:
							queue.append(j)
							visited[j] = True
							visitedCount += 1
		return -1


class Solution:

	def dfs(self, node, adj, vis):
		vis[node] = True
		for v in adj[node]:
			if vis[v] == False:
				self.dfs(v, adj, vis)

	def findMotherVertex(self, V, adj):
		vis = [False] * V
		ans = -1
		for i in range(V):
			if vis[i] == False:
				self.dfs(i, adj, vis)
				ans = i
		vis = [False] * V
		self.dfs(ans, adj, vis)
		for i in range(V):
			if vis[i] == False:
				return -1
		return ans


class Solution:

	def dfsutil(self, s, adj, visited):
		visited[s] = True
		for neighbour in adj[s]:
			if visited[neighbour] == False:
				self.dfsutil(neighbour, adj, visited)

	def findMotherVertex(self, v, adj):
		mother_vertex = 0
		visited = [False for i in range(v)]
		for i in range(v):
			if visited[i] == False:
				mother_vertex = i
				self.dfsutil(i, adj, visited)
		visited = [False for i in range(v)]
		self.dfsutil(mother_vertex, adj, visited)
		for x in visited:
			if x == False:
				return -1
		return mother_vertex


class Solution:

	def findMotherVertex(self, V, adj):
		visited = set()

		def dfs(node):
			if node in visited:
				return
			visited.add(node)
			for child in adj[node]:
				dfs(child)
		dfs(0)
		return 0 if len(visited) == V else -1


class Solution:

	def dfs(self, node, adj, vis, ans):
		vis.add(node)
		ans.append(node)
		for adjnode in adj[node]:
			if adjnode not in vis:
				self.dfs(adjnode, adj, vis, ans)

	def findMotherVertex(self, V, adj):
		vis = set()
		ans = []
		self.dfs(0, adj, vis, ans)
		if len(ans) == V:
			return 0
		return -1


class Solution:

	def findMotherVertex(self, v, adj):

		def recur(node):
			if node in visited:
				return
			visited.add(node)
			for i in adj[node]:
				recur(i)
			stack.append(node)

		def checkMother(node):
			if node in visited:
				return 0
			visited.add(node)
			ans = 1
			for i in adj[node]:
				ans += checkMother(i)
			return ans
		visited = set()
		stack = list()
		for i in range(v):
			if i not in visited:
				recur(i)
		mother = stack.pop()
		visited = set()
		if checkMother(mother) == v:
			return mother
		return -1


from collections import defaultdict, deque

class Solution:

	def dfs(self, node, adj, vis, ans):
		vis.add(node)
		ans.append(node)
		for adjnode in adj[node]:
			if adjnode not in vis:
				self.dfs(adjnode, adj, vis, ans)

	def findMotherVertex(self, V, adj):
		vis = set()
		for i in range(V):
			ans = []
			if i not in vis:
				self.dfs(i, adj, vis, ans)
				if len(ans) == V:
					return i
		return -1


class Solution:

	def findMotherVertex(self, V, adj):

		def dfs(start, adj, vis):
			vis[start] = True
			s[start] = True
			for el in adj[start]:
				if vis[el] == False:
					dfs(el, adj, vis)
		s = [False for i in range(V)]
		for i in range(V):
			if s[i] == False:
				vis = [False for i in range(V)]
				dfs(i, adj, vis)
			if vis == [True for _ in range(V)]:
				return i
		return -1


class Solution:

	def dfsUtils(self, i, visit, adj):
		visit[i] = True
		for nei in adj[i]:
			if visit[nei] == False:
				self.dfsUtils(nei, visit, adj)

	def findMotherVertex(self, V, adj):
		visit = [False] * V
		v = 0
		for i in range(V):
			if visit[i] == False:
				self.dfsUtils(i, visit, adj)
				v = i
		visit = [False] * V
		self.dfsUtils(v, visit, adj)
		if any((i == False for i in visit)):
			return -1
		else:
			return v


class Solution:

	def findMotherVertex(self, V, adj):
		visited = [False for i in range(V)]

		def dfs(node):
			visited[node] = True
			for v in adj[node]:
				if not visited[v]:
					dfs(v)
		lastNode = 0
		for i in range(V):
			if not visited[i]:
				dfs(i)
				lastNode = i
		visited = [False for i in range(V)]
		dfs(lastNode)
		if visited.count(False) > 0:
			return -1
		return lastNode


class Solution:

	def helper(self, adj, vis, sr):
		if vis[sr] == True:
			return sr
		vis[sr] = True
		for val in adj[sr]:
			Solution.helper(self, adj, vis, val)
		return sr

	def findMotherVertex(self, V, adj):
		vis = [False] * V
		store = 0
		for i in range(V):
			if vis[i] == False:
				store = Solution.helper(self, adj, vis, i)
		vi = [False] * V
		Solution.helper(self, adj, vi, store)
		for i in range(V):
			if vi[i] == False:
				return -1
		return store


class Solution:

	def findMotherVertex(self, V, adj):
		visited = [0] * V
		v = -1
		for i in range(V):
			if visited[i] == 0:
				findmin(i, adj, visited)
				v = i
		visited = [0] * V
		findmin(v, adj, visited)
		for i in visited:
			if i == 0:
				return -1
			else:
				return v

def findmin(s, edges, visited):
	visited[s] = 1
	for i in edges[s]:
		if visited[i] == 0:
			findmin(i, edges, visited)


class Solution:

	def dfs(self, u, adj, visited):
		visited[u] = True
		for v in adj[u]:
			if not visited[v]:
				self.dfs(v, adj, visited)

	def findMotherVertex(self, V, adj):
		visited = [False] * V
		last_finished_vertex = -1
		for u in range(V):
			if not visited[u]:
				self.dfs(u, adj, visited)
				last_finished_vertex = u
		visited = [False] * V
		self.dfs(last_finished_vertex, adj, visited)
		for u in range(V):
			if not visited[u]:
				return -1
		return last_finished_vertex


class Solution:

	def findMotherVertex(self, V, adj):
		visited = [False] * V
		for vertex in range(V):
			if not visited[vertex]:
				self.DFS(vertex, adj, visited)
				candidate_mother_vertex = vertex
		visited = [False] * V
		self.DFS(candidate_mother_vertex, adj, visited)
		if sum(visited) == V:
			return candidate_mother_vertex
		else:
			return -1

	def DFS(self, vertex, adj, visited):
		visited[vertex] = True
		for neigh in adj[vertex]:
			if not visited[neigh]:
				self.DFS(neigh, adj, visited)


class Solution:

	def findMotherVertex(self, V, adj):
		self.visited = [False] * V
		self.flag = False

		def dfs(ele, visited, count):
			visited[ele] = True
			for i in adj[ele]:
				if not visited[i]:
					dfs(i, visited, count)
		for i in range(V):
			self.flag = False
			self.visited = [False] * V
			dfs(i, self.visited, 0)
			if False not in self.visited:
				return i
		return -1


class Solution:

	def df(self, ind, v, adj):
		v[ind] = 1
		for i in adj[ind]:
			if v[i] == 0:
				self.df(i, v, adj)

	def findMotherVertex(self, V, adj):
		vertex = 0
		v = [0] * V
		for i in range(V):
			if v[i] == 0:
				self.df(i, v, adj)
				vertex = i
		v = [0] * V
		self.df(vertex, v, adj)
		if 0 in v:
			return -1
		else:
			return vertex


class Solution:

	def dfs_util(self, node, visited, adj):
		visited[node] = True
		for neighbor in adj[node]:
			if not visited[neighbor]:
				self.dfs_util(neighbor, visited, adj)

	def findMotherVertex(self, V, adj):
		visited = [False] * V
		last_visited = None
		for v in range(V):
			if not visited[v]:
				self.dfs_util(v, visited, adj)
				last_visited = v
		visited = [False] * V
		self.dfs_util(last_visited, visited, adj)
		for i in visited:
			if i == False:
				return -1
		return last_visited


class Solution:

	def findMotherVertex(self, V, adj):
		for v in range(V):
			visited = [False for _ in range(V)]
			stack = [v]
			c = 0
			while stack:
				node = stack.pop()
				c += 1
				visited[node] = True
				for neighbor in adj[node]:
					if not visited[neighbor]:
						stack.append(neighbor)
			if c == V:
				return v
		return -1


class Solution:

	def dfs_util(self, s, adj, vis):
		vis[s] = True
		for i in adj[s]:
			if not vis[i]:
				self.dfs_util(i, adj, vis)

	def findMotherVertex(self, V, adj):
		vis = [False for _ in range(V)]
		v = 0
		for i in range(V):
			if not vis[i]:
				self.dfs_util(i, adj, vis)
				v = i
		vis = [False for _ in range(V)]
		self.dfs_util(v, adj, vis)
		for s in vis:
			if not s:
				return -1
		return v


class Solution:

	def findMotherVertex(self, V, adj):
		ans = [0]
		q = [0]
		isVisited = [False] * V
		isVisited[0] = True
		temp = 0
		while q:
			temp = q.pop()
			for i in adj[temp]:
				if isVisited[i] == False:
					q.append(i)
					isVisited[i] = True
					ans.append(i)
		if len(ans) == V:
			return 0
		return -1


from collections import deque

class Solution:

	def dfs(self, i):
		self.vis[i] = 1
		for ele in self.adj[i]:
			if self.vis[ele] == 0:
				self.dfs(ele)

	def findMotherVertex(self, V, adj):
		n = V
		self.vis = [0] * n
		self.adj = adj
		for i in range(n):
			if self.vis[i] == 0:
				self.dfs(i)
				ver = i
		count = 0
		self.vis = [0] * n
		root = ver
		q = deque()
		q.append(root)
		self.vis[root] = 1
		while len(q):
			node = q.popleft()
			count += 1
			for ele in self.adj[node]:
				if self.vis[ele] == 0:
					q.append(ele)
					self.vis[ele] = 1
		if count == n:
			return ver
		else:
			return -1


class Solution:

	def findMotherVertex(self, V, adj):
		parent = 0
		visited = set()
		parent_set = set()
		for each in range(V):
			if each not in visited:
				self.dfs(each, adj, visited)
				parent = each
		visited.clear()
		self.dfs(parent, adj, visited)
		return -1 if len(visited) != V else parent

	def dfs(self, each, adj, visited):
		visited.add(each)
		for num in adj[each]:
			if num not in visited:
				self.dfs(num, adj, visited)


class Solution:

	def findMotherVertex(self, V, adj):

		def isMother(index, visited):
			for val in adj[index]:
				if visited[val] == 0:
					visited[val] = 1
					isMother(val, visited)

		def dfs(index, visited, stack):
			for val in adj[index]:
				if visited[val] == 0:
					visited[val] = 1
					dfs(val, visited, stack)
					stack.append(val)
		visited = [0] * V
		stack = []
		for i in range(V):
			if visited[i] == 0:
				visited[i] = 1
				dfs(i, visited, stack)
				stack.append(i)
		visited = [0] * V
		visited[stack[-1]] = 1
		isMother(stack[-1], visited)
		if sum(visited) == V:
			return stack[-1]
		return -1


class Solution:

	def dfsHelper(self, adj, source, visited):
		visited.add(source)
		for neighbor in adj[source]:
			if not neighbor in visited:
				self.dfsHelper(adj, neighbor, visited)

	def findMotherVertex(self, V, adj):
		previousSource = 0
		visited = set()
		for i in range(V):
			if not i in visited:
				self.dfsHelper(adj, i, visited)
				previousSource = i
		visited.clear()
		self.dfsHelper(adj, previousSource, visited)
		return -1 if len(visited) < V else previousSource


class Solution:

	def findMotherVertex(self, V, adj):
		stack = list()
		visited = [False for i in range(V)]
		for i in range(V):
			if not visited[i]:
				self.topo(V, adj, stack, visited, i)
		hold = stack.pop()
		stack = list()
		visited = [False for i in range(V)]
		self.topo(V, adj, stack, visited, hold)
		if all(visited):
			return hold
		else:
			return -1

	def topo(self, V, adj, stack, visited, target):
		visited[target] = True
		for data in adj[target]:
			if not visited[data]:
				self.topo(V, adj, stack, visited, data)
		stack.append(target)
		return None


class Solution:

	def dfs(self, adj, pos, vis):
		vis[pos] = True
		for i in adj[pos]:
			if not vis[i]:
				self.dfs(adj, i, vis)

	def findMotherVertex(self, V, adj):
		vis = [False for i in range(V)]
		last = 0
		for i in range(V):
			if not vis[i]:
				self.dfs(adj, i, vis)
				last = i
		vis = [False for i in range(V)]
		self.dfs(adj, last, vis)
		for i in vis:
			if i == False:
				return -1
		return last


class Solution:

	def findMotherVertex(self, V, adj):
		visited = []
		for i in range(V):
			visited.append(False)
		last_dfs = -1
		for i in range(V):
			if visited[i] == False:
				self.dfs(i, adj, visited)
				last_dfs = i
		for i in range(V):
			visited[i] = False
		self.dfs(last_dfs, adj, visited)
		for i in range(V):
			if visited[i] == False:
				return -1
		return last_dfs

	def dfs(self, start, adj, visited):
		visited[start] = True
		temp = adj[start]
		n = len(temp)
		for i in range(n):
			if visited[adj[start][i]] == False:
				self.dfs(adj[start][i], adj, visited)
		return


def dfs(u, visited, adj, count):
	count[0] += 1
	visited[u] = 1
	for e in adj[u]:
		if visited[e] == 0:
			dfs(e, visited, adj, count)

class Solution:

	def findMotherVertex(self, V, adj):
		visited = [0 for e in range(V)]
		for e in range(V):
			count = [0]
			if not visited[e]:
				dfs(e, visited, adj, count)
				if count[0] == V:
					return e
		return -1


class Solution:

	def findMotherVertex(self, V, adj):

		def dfs(u):
			visited.add(u)
			for v in adj[u]:
				if v not in visited:
					dfs(v)
		visited = set()
		cur = 0
		for i in range(V):
			if i not in visited:
				cur = i
				dfs(i)
		visited = set()
		dfs(cur)
		if len(visited) == V:
			return cur
		return -1


class Solution:

	def findMotherVertex(self, V, adj):
		visited = [False] * V
		v = 0
		for i in range(V):
			if visited[i] == False:
				self.DFS(i, adj, visited)
				v = i
		visited = [False] * V
		self.DFS(v, adj, visited)
		for i in range(V):
			if visited[i] == False:
				return -1
		return v

	def DFS(self, v, adj, visited):
		visited[v] = True
		for neig in adj[v]:
			if visited[neig] == False:
				self.DFS(neig, adj, visited)


from collections import deque

class Solution:

	def findMotherVertex(self, V, adj):

		def bfs(i, visited):
			q = deque([i])
			visited.add(i)
			while q:
				cur = q.popleft()
				for child in adj[cur]:
					if child not in visited:
						q.append(child)
						visited.add(child)
		visited = set()
		res = None
		for i in range(V):
			if i not in visited:
				bfs(i, visited)
				res = i
		visited = set()
		bfs(res, visited)
		if len(visited) == V:
			return res
		else:
			return -1


class Solution:

	def findMotherVertex(self, V, adj):
		for i in range(V):
			s = set()
			vis = [False] * V

			def mother(adj, j, s):
				s.add(j)
				vis[j] = True
				if len(s) == V:
					return True
				for k in adj[j]:
					if not vis[k]:
						if mother(adj, k, s):
							return True
			if mother(adj, i, s):
				return i
		return -1


class Solution:

	def dfs(self, u, vis, adj):
		vis[u] = True
		for v in adj[u]:
			if not vis[v]:
				self.dfs(v, vis, adj)

	def findMotherVertex(self, V, adj):
		vis = [False] * V
		last_vis = 0
		for i in range(V):
			if not vis[i]:
				last_vis = i
				self.dfs(i, vis, adj)
		vis = [False] * V
		self.dfs(last_vis, vis, adj)
		for i in vis:
			if not i:
				return -1
		return last_vis


class Solution:

	def findMotherVertex(self, V, adj):
		for i in range(V):
			vis = [0] * V
			x = self.bfs(i, adj, vis)
			return x

	def bfs(self, node, adj, vis):
		q = [node]
		while q:
			x = q.pop(0)
			vis[x] = 1
			for i in adj[x]:
				if vis[i] != 1:
					q.append(i)
					vis[i] = 1
		for j in vis:
			if j != 1:
				return -1
		return node


class Solution:

	def findMotherVertex(self, V, adj):
		visited = [False for i in range(V)]

		def solver(v):
			visited[v] = True
			for i in adj[v]:
				if visited[i] == False:
					solver(i)
		for i in range(V):
			if visited[i] == False:
				solver(i)
				v = i
		output = v
		visited = [False for i in range(V)]
		solver(output)
		if False not in visited:
			return output
		return -1


class Solution:

	def dfs(self, node):
		self.visited[node] = True
		self.count += 1
		for child in self.adj[node]:
			if not self.visited[child]:
				self.dfs(child)

	def findMotherVertex(self, V, adj):
		self.count = 0
		self.adj = adj
		self.visited = V * [False]
		for i in range(V):
			if self.visited[i]:
				continue
			self.dfs(i)
			if self.count == V:
				return i
			else:
				self.count = 0
		return -1


from collections import deque

class Solution:

	def findMotherVertex(self, V, adj):
		wholevisit = set()
		for i in range(V):
			if i not in wholevisit:
				q = deque()
				visited = set()
				q.append(i)
				visited.add(i)
			while q:
				cur = q.popleft()
				for nei in adj[cur]:
					if nei not in visited:
						q.append(nei)
						visited.add(nei)
			if len(visited) == V:
				return i
			else:
				wholevisit.update(visited)
		return -1


class Solution:

	def findMotherVertex(self, V, adj):
		visit = set()
		v = -1

		def dfs(adj, vertex, visit):
			visit.add(vertex)
			for edge in adj[vertex]:
				if edge not in visit:
					dfs(adj, edge, visit)
		for i in range(V):
			if i not in visit:
				dfs(adj, i, visit)
				v = i
		visit = set()
		dfs(adj, v, visit)
		if len(visit) != V:
			return -1
		return v


class Solution:

	def findMotherVertex(self, V, adj):
		visited = [False for i in range(V)]
		k = None
		for i in range(V):
			if visited[i] == False:
				self.dfs(visited, i)
				k = i
		visited = [False for i in range(V)]
		self.dfs(visited, k)
		for i in range(V):
			if visited[i] == False:
				return -1
		return k

	def dfs(self, visited, n):
		visited[n] = True
		for i in adj[n]:
			if visited[i] == False:
				self.dfs(visited, i)


class Solution:

	def findMotherVertex(self, V, adj):
		cnt = 0

		def dfs(root):
			nonlocal cnt
			visited[root] = True
			for node in adj[root]:
				if node not in visited:
					cnt += 1
					dfs(node)
		visited = {}
		for i in range(len(adj)):
			if i not in visited:
				res = dfs(i)
				if cnt == len(adj) - 1:
					return i
		return -1


class Solution:

	def findMotherVertex(self, V, adj):
		visited = [False] * V
		last_visited = -1
		for i in range(V):
			if not visited[i]:
				self.DFS(adj, i, visited)
				last_visited = i
		visited = [False] * V
		self.DFS(adj, last_visited, visited)
		return last_visited if all(visited) else -1

	def DFS(self, adj, u, visited):
		visited[u] = True
		for v in adj[u]:
			if not visited[v]:
				self.DFS(adj, v, visited)


class Solution:

	def findMotherVertex(self, V, adj):
		visited = [False] * V

		def dfs(v):
			if visited[v]:
				return
			visited[v] = True
			for nei in adj[v]:
				if not visited[nei]:
					dfs(nei)
		last = None
		for v in range(V):
			if not visited[v]:
				last = v
				dfs(v)
		visited = [False] * V
		dfs(last)
		return last if all(visited) else -1


class Solution:

	def findMotherVertex(self, V, adj):

		def bfs(node, adj, V):
			visit = [False] * V
			visit[node] = True
			q = [node]
			while q:
				cur = q.pop(0)
				for nei in adj[cur]:
					if not visit[nei]:
						visit[nei] = True
						q.append(nei)
			return node if all(visit) else -1
		for i in range(V):
			ans = bfs(i, adj, V)
			if ans != -1:
				return ans
		return -1


class Solution:

	def findMotherVertex(self, V, adj):
		mp = {}
		for i in range(V):
			mp[i] = adj[i]

		def dfs(v, i, mp):
			v[i] = True
			for node in mp[i]:
				if not v[node]:
					dfs(v, node, mp)
		for i in range(V):
			visited = [False] * V
			if not visited[i]:
				dfs(visited, i, mp)
				if False not in visited:
					return i
		return -1


from collections import defaultdict

class Solution:

	def execute_dfs(self, V, adj, s):
		global visited_global
		global visited
		global total
		total += 1
		visited_global[s] = True
		visited[s] = True
		for n in adj[s]:
			if visited_global[n] == False:
				self.execute_dfs(V, adj, n)

	def dfs(self, V, adj):
		global visited
		visited = [False] * V
		global visited_global
		global total
		for s in range(V):
			total = 0
			if visited[s] == False:
				visited_global = defaultdict(lambda : False)
				self.execute_dfs(V, adj, s)
			if total == V:
				return s
		return -1

	def findMotherVertex(self, V, adj):
		return self.dfs(V, adj)


class Solution:

	def findMotherVertex(self, V, adj):

		def dfsTraverse(s, adj, visited, dfs):
			q = [s]
			visited[s] = True
			while q:
				curr = q.pop(0)
				dfs.append(curr)
				for ngbr in adj[curr]:
					if not visited[ngbr]:
						visited[ngbr] = True
						q.append(ngbr)
		for i in range(V):
			visited = [False] * V
			dfs = []
			dfsTraverse(i, adj, visited, dfs)
			if len(dfs) == V:
				return i
		return -1


class Solution:

	def findMotherVertex(self, V, adj):

		def dfsF(node):
			vis[node] = 1
			for i in adj[node]:
				if not vis[i]:
					dfsF(i)
		vis = [0] * V
		v = 0
		for i in range(V):
			if not vis[i]:
				dfsF(i)
				v = i
		vis = [0] * V
		dfsF(v)
		if any((i == 0 for i in vis)):
			return -1
		else:
			return v


class Solution:

	def helper(self, v, visited):
		visited[v] = True
		for i in adj[v]:
			if visited[i] == False:
				self.helper(i, visited)

	def findMotherVertex(self, V, adj):
		visited = [False] * V
		v = 0
		i = 0
		while i < V:
			if visited[i] == False:
				self.helper(i, visited)
				v = i
			i += 1
		visited = [False] * V
		self.helper(v, visited)
		if any((i == False for i in visited)):
			return -1
		else:
			return v


class Solution:

	def DFSUtil(self, u, adj, visited):
		visited[u] = True
		for v in adj[u]:
			if not visited[v]:
				self.DFSUtil(v, adj, visited)
		return visited

	def findMotherVertex(self, V, adj):
		for i in range(V):
			visited = [False] * V
			ans = []
			if not visited[i]:
				ans = self.DFSUtil(i, adj, visited)
				if all(ans):
					return i
		return -1


class Solution:

	def dfs(self, adj, node, V):
		stack = [node]
		visited = [False for _ in range(V)]
		while stack:
			node = stack.pop()
			for children in adj[node]:
				if visited[children]:
					continue
				stack.append(children)
			visited[node] = True
		for i in range(V):
			if visited[i] == False:
				return False
		return True

	def findMotherVertex(self, V, adj):
		for i in range(V):
			if self.dfs(adj, i, V):
				return i
		return -1


class Solution:

	def findMotherVertex(self, V, adj):
		wholevisit = set()
		for i in range(V):
			if i not in wholevisit:
				q = []
				visited = set()
				q.append(i)
				visited.add(i)
				while q:
					cur = q.pop(0)
					for j in adj[cur]:
						if j not in visited:
							q.append(j)
							visited.add(j)
				if len(visited) == V:
					return i
				else:
					wholevisit.update(visited)
		return -1


class Solution:

	def findMotherVertex(self, V, adj):
		visted = [False] * V
		v = 0
		for i in range(V):
			if visted[i] == False:
				dfs(i, visted)
				v = i
		visted = [False] * V
		dfs(v, visted)
		if any((i == False for i in visted)):
			return -1
		else:
			return v

def dfs(i, visted):
	visted[i] = True
	for j in adj[i]:
		if visted[j] == False:
			dfs(j, visted)