Eulerian Path is a path in graph that visits every edge exactly once. Eulerian Circuit is an Eulerian Path which starts and ends on the same vertex. The task is to find that there exists the Euler Path or circuit or none in given undirected graph with V vertices and adjacency list adj.
Example 1:
Input: 
Output: 2
Explanation: The graph contains Eulerian circuit
Example 2:
Input: 
Output: 1
Explanation: The graph contains Eulerian path.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function isEulerCircuilt() which takes number of vertices in the graph denoting as V and adjacency list of graph denoting as adj and returns 1 if graph contains Eulerian Path, 2 if graph contains Eulerian Circuit 0 otherwise.
 
Expected Time Complexity: O(V+E) where E is the number of edges in graph.
Expected Space Complexity: O(V)
 
Constraints:
1 ≤ V, E ≤ 10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Graph algorithms

Data structures

Starter code: class Solution:

	def isEularCircuitExist(self, V, adj):

		#Code here

Solutions:
class Solution:

	def isEularCircuitExist(self, V, adj):
		even = 0
		for i in adj:
			even += len(i) % 2
		if even == 2:
			return 1
		if even == 0:
			return 2
		return 0


class Solution:

	def isEularCircuitExist(self, V, adj):
		c = 0
		for i in range(V):
			if len(adj[i]) % 2 != 0:
				c += 1
		if c == 0:
			return 2
		if c == 2:
			return 1
		return 0


class Solution:

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

	def is_connected(self, V, visited, adj):
		node = -1
		for i in range(V):
			if len(adj[i]):
				node = i
				break
		if node == -1:
			return True
		self.dfs(node, visited, adj)
		for i in range(V):
			if visited[i] == 0 and len(adj[i]) > 0:
				return False
		return True

	def isEularCircuitExist(self, V, adj):
		cnt_odd = 0
		for i in range(V):
			if len(adj[i]) % 2 != 0:
				cnt_odd += 1
		return 2 if cnt_odd == 0 else 1 if cnt_odd == 2 else 0


class Solution:

	def isEularCircuitExist(self, V, adj):
		count = 0
		for i in range(V):
			if len(adj[i]) % 2:
				count += 1
			if count == 3:
				return 0
		if count == 2:
			return 1
		if not count:
			return 2
		return 0


class Solution:

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

	def isEularCircuitExist(self, V, adj):
		degree = [0] * V
		for node in range(V):
			degree[node] += len(adj[node])
		oddCount = 0
		for node in range(V):
			if degree[node] % 2 != 0:
				oddCount += 1
		if not (oddCount == 0 or oddCount == 2):
			return 0
		visited = [False] * V
		for i in range(V):
			if degree[i] != 0:
				self.dfs(i, adj, visited)
				break
		for i in range(V):
			if degree[i] > 0 and (not visited[i]):
				return 0
		if oddCount == 2:
			return 1
		else:
			return 2


class Solution:

	def isEularCircuitExist(self, V, adj):
		indegree = [0] * V
		for i in range(V):
			for j in adj[i]:
				indegree[j] += 1
		odd = 0
		for i in range(V):
			if indegree[i] % 2 != 0:
				odd += 1
		if odd == 2:
			return 1
		if odd == 0:
			return 2
		return 0


class Solution:

	def isEularCircuitExist(self, V, adj):
		degree = [0] * V
		for node in range(V):
			for ngbhr in adj[node]:
				degree[ngbhr] += 1
		count_even = 0
		count_odd = 0
		for i in range(V):
			if degree[i] % 2 == 0:
				count_even += 1
			else:
				count_odd += 1
		if count_odd == 0:
			return 2
		if count_odd == 2:
			return 1
		return 0


from collections import deque

class Solution:

	def checkEularPath(self, V, adj):
		degree = 0
		odd = 0
		start = 0
		for i in range(V):
			degree = len(adj[i])
			if degree % 2 == 1:
				odd += 1
			if odd > 2:
				return -1
			if odd == 2:
				start = i
		return 2 if odd == 0 else start

	def check(self, adj, v, visited):
		for i in adj[v]:
			if visited[i] == 0:
				return i
		return -1

	def isEularCircuitExist(self, V, adj):
		ans = self.checkEularPath(V, adj)
		if ans == -1:
			return 0
		if ans == 2:
			return 2
		start = -1
		visited = [0] * V
		stack = deque()
		visited[ans] = 1
		child = self.check(adj, ans, visited)
		while stack or child != -1:
			if child == -1:
				if start == -1:
					start = ans
				ans = stack.pop()
			else:
				stack.append(ans)
				ans = child
				visited[child] = 1
				child = self.check(adj, ans, visited)
		return 2 if ans == start else 1


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

class Solution:

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

	def isEularCircuitExist(self, V, adj):
		d = defaultdict(list)
		degree = [0] * V
		for i in range(len(adj)):
			d[i] += adj[i]
			degree[i] += len(adj[i])
		visited = [False] * V
		src = -1
		for i in range(len(degree)):
			if degree[i] != 0:
				src = i
				break
		self.dfs(src, d, visited)
		for i in range(V):
			if visited[i] == False and degree[i] != 0:
				return 0
		oddDegree = 0
		for i in degree:
			if i & 1:
				oddDegree += 1
		if oddDegree == 0:
			return 2
		if oddDegree == 2:
			return 1
		return 0


import sys
sys.setrecursionlimit(10 ** 7)

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 is_all_edges_connected(self, V, adj):
		src = -1
		for u in range(V):
			if len(adj[u]) > 0:
				src = u
				break
		if src == -1:
			return True
		visited = [False for _ in range(V)]
		self.dfs(src, adj, visited)
		for u in range(V):
			if not visited[u] and len(adj[u]) > 0:
				return False
		return True

	def isEularCircuitExist(self, V, adj):
		if not self.is_all_edges_connected(V, adj):
			return 0
		odd = 0
		for u in range(V):
			deg = len(adj[u])
			if deg & 1:
				odd += 1
		if odd == 0:
			return 2
		elif odd == 2:
			return 1
		else:
			return 0


class Solution:

	def isEularCircuitExist(self, V, adj):
		degree = [len(nbs) for nbs in adj]
		odd_vertices = list(filter(lambda x: x % 2 == 1, degree))
		num_odd = len(odd_vertices)
		if num_odd not in [0, 2]:
			return 0
		if num_odd == 2:
			return 1
		return 2


import sys
sys.setrecursionlimit(1000000)

class Solution:

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

	def conected_graph(self, V, adj):
		visited = [False] * V
		node = -1
		for i in range(0, V):
			if len(adj[i]) > 1:
				node = i
				break
		if node == -1:
			return True
		self.DFS(node, visited, adj)
		for j in range(0, V):
			if visited[j] == False and len(adj[j]) > 0:
				return False
		return True

	def isEuler(self, V, adj):
		if not self.conected_graph(V, adj):
			return 0
		odd = 0
		for i in range(V):
			if len(adj[i]) % 2 != 0:
				odd += 1
		if odd == 0:
			return 2
		elif odd == 2:
			return 1
		elif odd > 2:
			return 0

	def isEularCircuitExist(self, V, adj):
		return self.isEuler(V, adj)


class Solution:

	def __findPath(self, curr_node, v):
		if self.deg[curr_node] > 0:
			for next_node in self.adj_mat[curr_node].keys():
				if self.adj_mat[curr_node][next_node] == 1:
					self.edges_covered += 1
					self.deg[curr_node] -= 1
					self.deg[next_node] -= 1
					self.adj_mat[curr_node][next_node] = 0
					self.adj_mat[next_node][curr_node] = 0
					self.__findPath(next_node, v)

	def isEularCircuitExist(self, v, adj):
		self.adj_mat = [{} for i in range(v)]
		self.deg = [0 for i in range(v)]
		e = 0
		for i in range(v):
			for j in adj[i]:
				e += 1
				self.deg[i] += 1
				self.deg[j] += 1
				self.adj_mat[i][j] = 1
				self.adj_mat[j][i] = 1
		e //= 2
		(start_node, od_dg_cnt, ans) = (None, 0, 1)
		for i in range(v):
			self.deg[i] //= 2
			if self.deg[i] % 2 != 0:
				od_dg_cnt += 1
				if od_dg_cnt > 2:
					return 0
				if start_node == None:
					start_node = i
		if start_node == None:
			(start_node, ans) = (0, 2)
		self.edges_covered = 0
		self.__findPath(start_node, v)
		return ans if self.edges_covered == e else 0


import sys
sys.setrecursionlimit(1000000)

def dfs(nod, visited, adj):
	visited[nod] = 1
	for i in adj[nod]:
		if visited[i] != 1:
			dfs(i, visited, adj)

def solve(v, adj):
	hold = -1
	for i in range(v):
		if len(adj[i]) > 0:
			hold = i
			break
	if hold == -1:
		return 2
	visited = [0 for i in range(v)]
	dfs(hold, visited, adj)
	nodd = 0
	for i in range(v):
		if len(adj[i]) > 0 and visited[i] == 0:
			return 0
		elif len(adj[i]) % 2 != 0:
			nodd += 1
	if nodd > 2:
		return 0
	if nodd == 0:
		return 2
	else:
		return 1

class Solution:

	def isEularCircuitExist(self, v, adj):
		return solve(v, adj)


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

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

	def isConnected(self, V, adj):
		vis = [False for i in range(V)]
		idx = 0
		for i in range(V):
			if len(adj[i]):
				idx = i
				break
		self.dfsUtil(i, vis, adj)
		for i in range(V):
			if vis[i] == False and len(adj[i]):
				return False
		return True

	def isEularCircuitExist(self, V, adj):
		if self.isConnected(V, adj) == False:
			return 0
		odd = 0
		for i in range(V):
			if len(adj[i]) & 1:
				odd = odd + 1
		if odd > 2:
			return 0
		elif odd:
			return 1
		return 2


class Solution:
	ans = 0

	def dfs(self, src, visited, graph, n, psf, oz_src):
		if psf == n - 1:
			self.ans = 1
			circuit = False
			for adj in graph[src]:
				if adj == oz_src:
					circuit = True
					break
			if circuit:
				self.ans = 2
		visited.add(src)
		for adj in graph[src]:
			if adj not in visited:
				self.dfs(adj, visited, graph, n, psf + 1, oz_src)
		visited.remove(src)

	def isEularCircuitExist(self, V, adj):
		odd = 0
		for i in range(V):
			if len(adj[i]) & 1:
				odd += 1
		if odd == 0:
			return 2
		elif odd == 2:
			return 1
		else:
			return 0
		visited = set()
		for i in range(V):
			self.dfs(i, visited, adj, V, 0, i)
			if self.ans == 2:
				return self.ans
		return self.ans


class Solution:

	def is_cycle(self, src, graph, visited, parent):
		visited[src] = True
		for adj in graph[src]:
			if visited[adj]:
				return 1
			if not visited[adj]:
				val = self.is_cycle(adj, graph, visited, src)
				if val == 1:
					return 1
				elif val == 2:
					return 2
				elif val == 0:
					return 0
			elif parent != adj:
				return 2
		return 0

	def isEularCircuitExist(self, V, adj):
		odd = 0
		for i in range(V):
			if len(adj[i]) % 2 != 0:
				odd += 1
		if odd == 0:
			return 2
		elif odd == 2:
			return 1
		elif odd > 2:
			return 0


class Solution:

	def isEularCircuitExist(self, V, adj):
		odd = 0
		for i in range(V):
			if len(adj[i]) % 2 != 0:
				odd += 1
		if odd == 2:
			return 1
		elif odd == 0:
			return 2
		else:
			return 0


class Solution:

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

	def isEularCircuitExist(self, V, adj):
		count_v = [0] * V
		count_v = [len(i) for i in adj]
		all_conn = []
		odd_count = 0
		for i in range(V):
			if count_v[i] != 0:
				all_conn.append(i)
			if count_v[i] % 2 != 0:
				odd_count += 1
		if odd_count != 2:
			if odd_count != 0:
				return 0
		visited = [0] * V
		self.dfs(all_conn[0], adj, visited)
		for i in all_conn:
			if visited[i] == 0:
				return 0
		if odd_count == 2:
			return 1
		else:
			return 2


class Solution:

	def isEularCircuitExist(self, n, x):
		odd = 0
		even = 0
		for i in x:
			if len(i) % 2 == 0:
				even += 1
			else:
				odd += 1
		if even == n:
			return 2
		if odd <= 2:
			return 1
		return 0


class Solution:

	def isEularCircuitExist(self, V, adj):
		d = [0 for _ in range(V)]
		for i in range(V):
			d[i] += len(adj[i])
		A = [0, 0]
		for i in range(V):
			A[d[i] % 2] += 1
		if A[0] == V:
			return 2
		elif A[0] == V - 2:
			return 1
		return 0


class Solution:

	def isEularCircuitExist(self, V, adj):
		deg = {}
		for k in range(len(adj)):
			deg[k] = len(adj[k])
		lst = [k for k in deg.keys() if deg[k] % 2 == 1]
		if len(lst) == 0:
			return 2
		if len(lst) == 2:
			return 1
		return 0


class Solution:

	def isEularCircuitExist(self, V, adj):
		p = 0
		q = 0
		for i in range(V):
			if len(adj[i]) % 2 == 0:
				p += 1
			else:
				q += 1
		if q == 2:
			return 1
		elif p == V:
			return 2
		else:
			return 0
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(V, E) = map(int, input().strip().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.isEularCircuitExist(V, adj)
		print(ans)


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def isEularCircuitExist(self, V, adjacencyList):

		def dfs(s, visited):
			visited[s] = 1
			for adj in adjacencyList[s]:
				if visited[adj] == 0:
					dfs(adj, visited)

		def connected_graph():
			visited = [0 for _ in range(V)]
			node = -1
			for s in range(V):
				if len(adjacencyList[s]) > 0:
					node = s
					break
			if node == -1:
				return True
			dfs(node, visited)
			for s in range(V):
				if visited[s] == 0 and len(adjacencyList[s]) > 0:
					return False
			return True
		if not connected_graph():
			return 0
		odd = 0
		for s in range(V):
			if len(adjacencyList[s]) & 1:
				odd += 1
		if odd > 2:
			return 0
		return 2 if odd == 0 else 1
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(V, E) = map(int, input().strip().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.isEularCircuitExist(V, adj)
		print(ans)


class Solution:

	def isEularCircuitExist(self, V, adj):
		count = 0
		for i in range(V):
			if len(adj[i]) % 2 != 0 and count > 2:
				return 0
			elif len(adj[i]) % 2 != 0:
				count += 1
		if count == 0:
			return 2
		if count == 2:
			return 1


class Solution:

	def isEularCircuitExist(self, V, adj):
		degrees = [0] * V
		evndeg = 0
		for i in range(V):
			degrees[i] = len(adj[i])
			if degrees[i] % 2:
				evndeg += 1
		ans = 0
		visited = [0] * V
		top = 0
		for i in range(V):
			if degrees[i]:
				stack = [i]
				top += 1
				break
		while top:
			val = stack.pop()
			top -= 1
			visited[val] = 1
			for i in adj[val]:
				if not visited[i] and degrees[i]:
					top += 1
					stack.append(i)
		con = True
		for i in range(V):
			if not visited[i] and degrees[i]:
				con = False
		if con and evndeg == 0:
			ans = 2
		if con and evndeg == 2:
			ans = 1
		return ans


from collections import deque

class Solution:

	def odd_degree_check(self, V, degree):
		count = 0
		for v in range(V):
			if degree[v] % 2 != 0:
				count = count + 1
		return count

	def bfs_check(self, src, V, degree, adj):
		q = deque()
		visited = set()
		q.append(src)
		visited.add(src)
		while q:
			v = q.popleft()
			for adj_v in adj[v]:
				if adj_v not in visited:
					q.append(adj_v)
					visited.add(adj_v)
		for v in range(V):
			if v not in visited and degree[v] > 0:
				return False
		return True

	def check_connectivity(self, V, degree, adj):
		for v in range(V):
			if degree[v] == 0:
				continue
			if not self.bfs_check(v, V, degree, adj):
				return False
		return True

	def isEularCircuitExist(self, V, adj):
		degree = [0] * V
		for v in range(V):
			degree[v] = len(adj[v])
		if self.check_connectivity(V, degree, adj) and self.odd_degree_check(V, degree) == 0:
			return 2
		if self.check_connectivity(V, degree, adj) and self.odd_degree_check(V, degree) == 2:
			return 1
		return 0


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def isEularCircuitExist(self, V, adj):

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

		def is_connected(adj, V):
			visit = [False] * V
			node = -1
			for i in range(V):
				if len(adj[i]) > 0:
					node = i
					break
			if node == -1:
				return True
			dfs(adj, visit, node)
			for i in range(V):
				if visit[i] == False and len(adj[i]) > 0:
					return False
			return True
		if not is_connected(adj, V):
			return 0
		od = 0
		for i in range(V):
			if len(adj[i]) & 1:
				od += 1
		if od > 2:
			return 0
		return 2 if od == 0 else 1


class Solution:

	def isEularCircuitExist(self, V, adj):
		import sys
		sys.setrecursionlimit(11000001)
		degree = [len(adj[i]) for i in range(V)]
		i = 0
		while i < V:
			if degree[i] > 0:
				break
			i += 1
		if i == V:
			return 2
		visited = [False] * V

		def DFS(i):
			visited[i] = True
			for x in adj[i]:
				if not visited[x]:
					DFS(x)
		DFS(i)
		count = 0
		for i in range(V):
			if degree[i] != 0 and (not visited[i]):
				return 0
			count += degree[i] % 2
		if count == 2:
			return 1
		elif count == 0:
			return 2
		else:
			return 0


class Solution:

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

	def isEularCircuitExist(self, V, adj):
		odd_degree_count = 0
		for i in range(V):
			if len(adj[i]) % 2 == 1:
				odd_degree_count += 1
		if odd_degree_count == 0:
			return 2
		if odd_degree_count == 2:
			return 1
		return 0


from collections import defaultdict

class Solution:

	def isEularCircuitExist(self, V, adj):
		conns = defaultdict(lambda : [])
		for (ind, node2) in enumerate(adj):
			conns[ind] += node2
		degrees = defaultdict(lambda : 0)
		for (node, children) in conns.items():
			degrees[node] += len(children)

		def isCircuit(degrees):
			for (node, degree) in degrees.items():
				if degree % 2 != 0:
					return False
			return True

		def isPath(degrees):
			count = 0
			for (node, degree) in degrees.items():
				if degree % 2 != 0:
					count += 1
			if count == 0 or count == 2:
				return True
			return False
		if isCircuit(degrees):
			return 2
		if isPath(degrees):
			return 1
		return 0


import sys
sys.setrecursionlimit(100000)

class Solution:

	def isEularCircuitExist(self, V, adj):
		degree = [0 for _ in range(V)]
		for i in range(V):
			for an in adj[i]:
				degree[an] += 1
		vis = [False for _ in range(V)]

		def dfs(node):
			vis[node] = True
			for an in adj[node]:
				if not vis[an]:
					dfs(an)
		tmp = None
		for i in range(V):
			if degree[i] > 0:
				tmp = i
				break
		if tmp == None:
			return 1
		dfs(tmp)
		flag = 0
		for i in range(V):
			if not vis[i] and degree[i] == 0:
				flag = 1
			elif not vis[i] and degree[i] > 0:
				flag = 2
				break
		if flag == 1:
			return 1
		if flag == 2:
			return 0
		cnt = 0
		for i in range(V):
			if degree[i] % 2 != 0:
				cnt += 1
		if cnt == 0:
			return 2
		if cnt == 2:
			return 1
		return 0


import sys
sys.setrecursionlimit(10 ** 5)

class Solution:

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

	def isConnected(self, V, adj):
		visited = [False] * V
		k = 0
		for k in range(V):
			if len(adj[k]) > 0:
				break
		self.dfs(k, V, adj, visited)
		for i in range(V):
			if not visited[i] and len(adj[i]) != 0:
				return False
		return True

	def isEularCircuitExist(self, V, adj):
		if not self.isConnected(V, adj):
			return 0
		odd = 0
		for i in range(V):
			if len(adj[i]) % 2 != 0:
				odd += 1
		if odd == 0:
			return 2
		if odd == 2:
			return 1
		return 0


class Solution:

	def isEularCircuitExist(self, V, adj):
		odd = 0
		for item in adj:
			if len(item) % 2 == 1:
				odd += 1
		if odd > 2:
			return 0
		elif odd == 0:
			return 2
		return 1


from collections import deque

class Solution:

	def dfs(self, v, visited, adj):
		queue = deque()
		queue.append(v)
		while queue:
			p = queue.popleft()
			visited[p] = True
			for i in adj[p]:
				if not visited[i]:
					queue.append(i)

	def isConnected(self, ajd, V):
		visited = [False for i in range(V)]
		for i in range(V):
			if len(adj[i]) > 1:
				break
		if i == V - 1:
			return True
		self.dfs(i, visited, adj)
		for i in range(V):
			if not visited[i] and len(adj[i]) > 0:
				return False
		return True

	def isEularCircuitExist(self, V, adj):
		if not self.isConnected(adj, V):
			return 0
		odd = 0
		for i in range(V):
			if len(adj[i]) % 2 != 0:
				odd += 1
		if odd == 0:
			return 2
		if odd == 2:
			return 1
		return 0


class Solution:

	def isEularCircuitExist(self, V, adj):
		odd_degree = 0
		for neighbors in adj:
			if len(neighbors) % 2 != 0:
				odd_degree += 1
		if odd_degree == 0:
			return 2
		elif odd_degree == 2:
			return 1
		else:
			return 0


def dfs(g, u):
	global visited
	visited[u] = True
	for v in g[u]:
		if visited[v] == False:
			dfs(g, v)

def isConnected(g, n):
	global visited
	visited = [False for i in range(n)]
	for i in range(n):
		if len(g[i]) > 0:
			try:
				dfs(g, i)
				break
			except:
				return 0
	else:
		return True
	for i in range(n):
		if visited[i] == False and len(g[i]) > 0:
			return False
	return True

def solve(g, n):
	if isConnected(g, n) == False:
		return 0
	odd = 0
	for i in range(n):
		if len(g[i]) % 2 != 0:
			odd = odd + 1
	if odd > 2:
		return 0
	if odd == 2:
		return 1
	return 2

class Solution:

	def isEularCircuitExist(self, V, adj):
		return solve(adj, V)


class Solution:

	def isEularCircuitExist(self, V, adj):
		parent = [0 for _ in range(V)]
		for i in range(V):
			for s in adj[i]:
				parent[s] += 1
		odd = 0
		even = 0
		for i in range(V):
			if parent[i] % 2 == 1:
				odd += 1
		if odd == 2:
			return 1
		elif odd > 2:
			return 0
		return 2


class Solution:

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

	def connected(self, V, adj):
		visited = [False] * V
		v = -1
		for i in range(V):
			if len(adj[i]) > 0:
				v = i
				break
		if v == -1:
			return True
		self.dfs(visited, v, adj)
		for i in range(V):
			if visited[i] == False and len(adj[i]) > 0:
				return False
		return True

	def iseuler(self, V, adj):
		if self.connected == False:
			return 0
		odd = 0
		for i in range(V):
			if len(adj[i]) % 2 != 0:
				odd += 1
		if odd == 0:
			return 2
		elif odd == 2:
			return 1
		else:
			return 0

	def isEularCircuitExist(self, V, adj):
		return self.iseuler(V, adj)


class Solution:

	def isEularCircuitExist(self, V, adj):
		degrees = [0] * V
		odd = 0
		for paths in adj:
			for path in paths:
				degrees[path] += 1
		for deg in degrees:
			if deg & 1 != 0:
				odd += 1
		if odd > 2:
			return 0
		elif odd == 2:
			return 1
		return 2


class Solution:

	def isEularCircuitExist(self, V, adj):
		in_degree = [0] * V
		out_degree = [0] * V
		degree = [0] * V
		for node in range(V):
			degree[node] += len(adj[node])
		odd = 0
		for x in degree:
			if x % 2 == 0:
				continue
			else:
				odd += 1
		if odd == 0:
			return 2
		if odd == 2:
			return 1
		return 0


import sys
sys.setrecursionlimit(10 ** 8)

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

class Solution:

	def isEularCircuitExist(self, n, adj):
		visited = [False for _ in range(n)]
		indegree = [0 for _ in range(n)]
		for i in range(n):
			neis = adj[i]
			for nei in neis:
				indegree[nei] += 1
		for i in range(n):
			if indegree[i] != 0:
				src = i
				break
		dfs(visited, adj, src)
		for i in range(n):
			if not visited[i] and indegree[i] >= 1:
				return 0
		oddC = 0
		eveC = 0
		for i in range(n):
			if indegree[i] % 2 == 1:
				oddC += 1
			if indegree[i] % 2 == 0:
				eveC += 1
			if oddC > 2:
				return 0
		if oddC == 2 and eveC == n - 2:
			return 1
		if oddC == 0 and eveC == n:
			return 2


class Solution:

	def isEularCircuitExist(self, V, adj):
		self.adj = adj
		self.vzd = [False] * V
		self.E = 0
		nood = self.oddc()
		if nood > 2:
			return 0
		for v in range(V):
			if len(adj[v]):
				self.explore(v)
				break
		if self.E < E << 1:
			return 0
		if not nood:
			return 2
		return 1

	def oddc(self):
		cnter = 0
		for nbors in self.adj:
			if len(nbors) & 1:
				cnter += 1
		return cnter

	def explore(self, u):
		self.vzd[u] = True
		self.E += len(adj[u])
		for v in adj[u]:
			if not self.vzd[v]:
				self.explore(v)


class Solution:

	def isEularCircuitExist(self, V, adj):
		e_count = 0
		o_count = 0
		for n in range(0, V):
			if len(adj[n]) % 2 == 0:
				e_count += 1
			else:
				o_count += 1
		if e_count == V:
			return 2
		elif o_count == 0 or o_count == 2:
			return 1
		else:
			return 0


class Solution:

	def isEularCircuitExist(self, V, adj):
		path = 0
		circuit = 0
		odd = 0
		for i in range(V):
			if len(adj[i]) % 2 == 1:
				odd += 1
		if odd == 0 or odd == 2:
			path = 1
		if odd == 0:
			circuit = 1
		return path + circuit


class Solution:

	def isEularCircuitExist(self, V, adj):
		freq = [0] * V
		for i in range(V):
			for x in adj[i]:
				freq[x] += 1
		odd = 0
		for j in range(V):
			if freq[j] % 2 != 0:
				odd += 1
		path = 0
		circuit = 0
		if odd == 0 or odd == 2:
			path = 1
		if odd == 0:
			circuit = 1
		return path + circuit