Eulerian Path is a path in a graph that visits every edge exactly once. Eulerian Circuit is an Eulerian Path that starts and ends on the same vertex. Given the number of vertices V and adjacency list adj denoting the graph. Your task is to find that there exists the Euler circuit or not
Note that: Given graph is connected.
Example 1:
Input: 
Output: 1
Explanation: One of the Eularian circuit 
starting from vertex 0 is as follows:
0->1->3->2->0
 
Your Task:
You don't need to read or print anything. Your task is to complete the function isEularCircuitExist() which takes V and adjacency list adj as input parameter and returns boolean value 1 if Eular circuit exists otherwise returns 0.
 
Expected Time Complexity: O(V + E)
Expected Space Complexity: O(V)
 
Constraints:
1 <= V <= 10^{5}
1 <= E <= 2*10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Graph algorithms

Data structures

Graph traversal

Starter code: class Solution:

	def isEularCircuitExist(self, V, adj):

		#Code here

Solutions:
class Solution:

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

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

	def isEularCircuitExist(self, V, adj):
		visited = [-1] * V
		if not self.connected_graph(visited, adj, V):
			return 0
		for i in range(V):
			if len(adj[i]) % 2 != 0:
				return 0
		return 1


class Solution:

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


class Solution:

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


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 isEularCircuitExistOLD(self, V, adj):
		visited = [0] * V
		if not self.is_connected(V, visited, adj):
			return 0
		cnt_odd = 0
		for i in range(V):
			if visited[i] and len(adj[i]) % 2 != 0:
				cnt_odd += 1
		return 1 if cnt_odd == 0 else 0

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


import sys

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):
		sys.setrecursionlimit(10 ** 6)
		visited = [False] * V
		degree = [0] * V
		for node in range(V):
			degree[node] += len(adj[node])
		for node in range(V):
			if degree[node] != 0:
				if degree[node] % 2 == 0:
					self.dfs(node, adj, visited)
				else:
					return False
		for node in range(V):
			if degree[node] != 0:
				if not visited[node]:
					return False
		return True


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 indegree:
			if i % 2 != 0:
				odd += 1
		if odd == 0:
			return 1
		return 0


class Solution:

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

	def isConnected(self, n, adj):
		visited = [False for i in range(n)]
		i = 0
		while i < n:
			if len(adj[i]) != 0:
				break
			i += 1
		if i == n:
			return True
		self.DFSutil(i, visited, adj)
		for i in range(n):
			if visited[i] == False and len(adj[i]) > 0:
				return False
		return True

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


class Solution:

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


class Solution:

	def isEularCircuitExist(self, n, x):
		return int(all((not len(i) & 1 for i in x)))


class Solution:

	def isEularCircuitExist(self, n, x):
		return int(all((not len(i) & 1 for i in x)))

		def f(i):
			st.append(i)
			vv.add(i)
			dd.add(i)
			while x[i]:
				a = x[i].pop(0)
				if (i, a) in v or (a, i) in v:
					continue
				v.add((i, a))
				f(a)
		v = set()
		vv = set()
		st = []
		for i in range(n):
			if i not in vv:
				dd = set()
				st = []
				f(i)
				edg = sum((len(x[i]) for i in dd))
				if not (st[0] == st[-1] and edg == 0):
					return 0
		return 1


class Solution:

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


class Solution:

	def isEularCircuitExist(self, V, adj):
		indegree = [0] * V
		for i in range(V):
			for j in adj[i]:
				indegree[j] += 1
		count = 0
		for i in indegree:
			if i & 1:
				count += 1
		if count == 0:
			return 1
		return 0
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.isEularCircuitExist(V, adj)
		if ans:
			print('1')
		else:
			print('0')


class Solution:

	def isEularCircuitExist(self, n, adj):
		return all((len(i) % 2 == 0 for i in adj))
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.isEularCircuitExist(V, adj)
		if ans:
			print('1')
		else:
			print('0')


class Solution:

	def dfs(self, u, adj, used, eu, ev, ans):
		while len(adj[u]):
			e = adj[u].pop()
			if used[e]:
				continue
			used[u] = True
			self.dfs(eu[e] ^ ev[e] ^ u, adj, used, eu, ev, ans)
			ans.append(u)

	def isEularCircuitExist(self, V, adj):
		st = set(tuple([-1, -1]))
		eu = []
		ev = []
		ans = []
		used = [False for i in range(V)]
		for i in range(V):
			for j in range(len(adj[i])):
				u = i
				v = adj[i][j]
				if len(st) and (tuple([u, v]) in st or tuple([v, u]) in st):
					continue
				eu.append(u)
				ev.append(v)
				st.add(tuple([u, v]))
		adj1 = [[] for i in range(V)]
		for i in range(len(eu)):
			adj1[eu[i]].append(i)
			adj1[ev[i]].append(i)
		for i in range(V):
			if len(adj[i]) & 1:
				return False
		ans.append(0)
		self.dfs(0, adj1, used, eu, ev, ans)
		if len(ans) ^ len(eu) + 1:
			return False
		return True


class Solution:

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


class Solution:

	def isEularCircuitExist(self, V, adj):
		for i in range(V):
			if len(adj[i]) % 2 == 1:
				return False
		visited = set()

		def dfs(node=0):
			if node in visited:
				return
			visited.add(node)
			for x in adj[node]:
				dfs(x)
		compsWithEdges = 0
		for i in range(V):
			compsWithEdges += i not in visited and len(adj[i]) != 0
			if compsWithEdges == 2:
				return False
			dfs(i)
		return True


class Solution:

	def isEularCircuitExist(self, n, adj):
		return all((len(i) % 2 == 0 for i in adj))


class Solution:

	def isEularCircuitExist(self, V, adj):
		edges = []
		for i in range(V):
			edges.append(sum(adj[i]))
		start = odd = 0
		for i in range(V):
			if len(adj[i]) % 2 == 1:
				odd += 1
		if odd == 0:
			return 1
		else:
			return 0


class Solution:

	def isEularCircuitExist(self, V, adj):
		inEdge = [0 for _ in range(V)]
		for i in range(V):
			for x in adj[i]:
				inEdge[i] += 1
		cnt = 0
		for i in range(V):
			if inEdge[i] % 2 == 1:
				cnt += 1
		if cnt > 0:
			return 0
		return 1


class Solution:

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


class Solution:

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


class Solution:

	def __init__(self):
		self.v = []

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

	def isEularCircuitExist(self, V, adj):
		for i in range(len(adj)):
			self.v.append(False)
		c = 0
		for i in range(len(adj)):
			if self.v[i] == False and len(adj[i]) > 0:
				c += 1
				self.dfs(i, adj)
		if c == 2:
			return 0
		for i in range(len(adj)):
			if len(adj[i]) % 2 != 0:
				return 0
		return 1


class Solution:

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

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

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


class Solution:

	def isEularCircuitExist(self, V, adj):
		node = [0 for i in range(V)]
		for i in range(V):
			for j in adj[i]:
				node[j] += 1
		temp = 0
		for i in range(V):
			if node[i] % 2 == 1:
				temp += 1
		if temp > 0:
			return 0
		return 1


class Solution:

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

	def isEularCircuitExist(self, V, adj):
		if E == 0:
			return True
		cnt = 0
		visited = [False] * V
		for i in range(V):
			if visited[i] == False:
				cnt += 1
				if cnt > 1:
					return False
				self.dfs(adj, i, visited)
		for i in range(V):
			if len(adj[i]) % 2 != 0:
				return False
		return True


class Solution:

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

	def transpose(self, V, adj):
		g = [[] for i in range(V)]
		for i in range(V):
			g.append([])
		for i in range(V):
			for j in adj[i]:
				g[j].append(i)
		return g

	def isEularCircuitExist(self, V, adj):
		visited = [0] * V
		v = 0
		for v in range(V):
			if len(adj[v]) > 0:
				break
		self.DFSUtil(v, visited, adj)
		for i in range(len(visited)):
			if visited[i] == 0 and len(adj[i]) > 0:
				return False
		for i in range(V):
			if len(adj[i]) % 2 != 0:
				return False
		return True


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

def eularCircut(g):
	global visited
	n = len(g)
	visited = [False for i in range(n)]
	for i in range(n):
		if len(g[i]) > 0:
			dfs(g, i)
			break
	for i in range(n):
		if visited[i] == False and len(g[i]) > 0:
			return False
	for i in range(n):
		if len(g[i]) % 2 != 0:
			return False
	return True

class Solution:

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


class Solution:

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

def dfs(V, adj, visited, i):
	visited[i] = 1
	for j in adj[i]:
		if visited[j] == 0:
			dfs(V, adj, visited, j)

def connected(V, adj):
	components = 0
	visited = [0 for i in range(V)]
	for i in range(V):
		if visited[i] == 0:
			dfs(V, adj, visited, i)
			compontens += 1
	if components == 1:
		return True
	else:
		return False


class Solution:

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


class Solution:

	def isEularCircuitExist(self, V, adj):
		visited = [False for i in range(V)]
		sv = -1
		odd = 0
		for i in range(V):
			if len(adj[i]) % 2 != 0:
				return 0
		return 1
		if odd > 2:
			return 0
		flag = False
		for i in range(V):
			if len(adj[i]) > 0:
				sv = i
				break
		if sv == -1:
			return 1
		self.doDFS(sv, visited, adj, flag)
		for i in range(V):
			if len(adj[i]) > 0 and visited[i] == False:
				return 0
		return 1

	def doDFS(self, sv, visited, adj, flag):
		visited[sv] = True
		for i in adj[sv]:
			if visited[i] == False:
				self.doDFS(i, visited, adj, True)
		return


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 1
		else:
			return 0

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


class Solution:

	def isEularCircuitExist(self, V, adj):
		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:
				return 0
		return 1


class Solution:

	def isEularCircuitExist(self, V, adj):
		for ed in adj:
			if len(ed) % 2:
				return False
		return True


class Solution:

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

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

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