Given a graph with n vertices, e edges and an array arr[] denoting the edges connected to each other, check whether it is Biconnected or not.
Note: The given graph is Undirected.
 
Example 1:
Input:
n = 2, e = 1
arr = {0, 1}
Output:
1
Explanation:
       0
      /
     1
The above graph is Biconnected.
Example 2:
Input:
n = 3, e = 2
arr = {0, 1, 1, 2}
Output:
0
Explanation:
       0
      /
     1
      \
       2
The above graph is not Biconnected.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function biGraph() which takes 2 Integers n, and e and an array arr of length 2*e as input and returns 1 if the graph is biconnected else returns 0.
 
Expected Time Complexity: O(n+e)
Expected Auxiliary Space: O(n)
 
Constraints:
1 <= e <= 100
2 <= n <= 100

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Graph algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

    def biGraph(self, arr, n, e):

        # code here 

Solutions:
class Solution:

	def dfs(self, adj, v, p=-1):
		if self.ans:
			return
		self.marked[v] = 1
		self.low[v] = self.time
		self.tin[v] = self.time
		self.time += 1
		children = 0
		for w in adj[v]:
			if w == p:
				continue
			if self.marked[w]:
				self.low[v] = min(self.low[v], self.tin[w])
			else:
				self.dfs(adj, w, v)
				children += 1
				self.low[v] = min(self.low[v], self.low[w])
				if self.low[w] >= self.tin[v] and p != -1:
					self.ans = True
					return
		if p == -1 and children > 1:
			self.ans = True

	def biGraph(self, arr, n, e):
		adj = [[] for _ in range(n)]
		for i in range(e):
			adj[arr[2 * i]].append(arr[2 * i + 1])
			adj[arr[2 * i + 1]].append(arr[2 * i])
		self.marked = [0 for _ in range(n)]
		self.tin = [-1 for _ in range(n)]
		self.low = [-1 for _ in range(n)]
		self.time = 0
		self.ans = False
		self.dfs(adj, 0)
		return 0 if self.ans or 0 in self.marked else 1


time = 0

def articulation(graph, v, disc, low, parent, visited):
	global time
	disc[v] = time
	low[v] = time
	visited[v] = True
	time += 1
	child = 0
	for i in graph[v]:
		if not visited[i]:
			parent[i] = v
			if articulation(graph, i, disc, low, parent, visited):
				return True
			low[v] = min(low[v], low[i])
			child += 1
			if parent[v] == -1 and child > 1:
				return True
			if parent[v] != -1 and low[i] >= disc[v]:
				return True
		elif i != parent[v]:
			low[v] = min(low[v], disc[i])
	return False

class Solution:

	def biGraph(self, arr, n, e):
		disc = [-1] * n
		low = [-1] * n
		parent = [-1] * n
		visited = [False] * n
		c = 0
		graph = [[] for i in range(n)]
		for i in range(0, e * 2, 2):
			graph[arr[i]].append(arr[i + 1])
			graph[arr[i + 1]].append(arr[i])
		if articulation(graph, 0, disc, low, parent, visited):
			return 0
		if any((i == False for i in visited)):
			return 0
		return 1


class Solution:
	time = 0

	def biGraph(self, arr, n, e):
		adj = [[] for i in range(n)]
		for i in range(0, 2 * e, 2):
			adj[arr[i]].append(arr[i + 1])
			adj[arr[i + 1]].append(arr[i])
		disc = [-1 for i in range(n)]
		low = [-1 for i in range(n)]
		parent = [-1 for i in range(n)]
		ap = [False for i in range(n)]
		c = 0
		for i in range(n):
			if disc[i] == -1:
				c += 1
				self.DFS(i, disc, low, parent, ap, adj)
		if c > 1 or True in ap:
			return 0
		return 1

	def DFS(self, u, disc, low, parent, ap, adj):
		(disc[u], low[u]) = (Solution.time, Solution.time)
		Solution.time += 1
		child = 0
		for v in adj[u]:
			if disc[v] == -1:
				child += 1
				parent[v] = u
				self.DFS(v, disc, low, parent, ap, adj)
				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 v != parent[u]:
				low[u] = min(low[u], disc[v])


class Solution:

	def biGraph(self, y, n, e):
		x = [[] for i in range(n)]
		for i in range(0, len(y), 2):
			(a, b) = (y[i], y[i + 1])
			x[a].append(b)
			x[b].append(a)
		found = False
		v = set()
		disc = {}
		low = {}
		t = 0

		def f(i, p=-1):
			nonlocal found, t
			if found:
				return
			v.add(i)
			disc[i] = t
			low[i] = t
			t += 1
			child = 0
			for j in x[i]:
				if j != p:
					if j in v:
						low[i] = min(low[i], disc[j])
					else:
						f(j, i)
						if found:
							return
						low[i] = min(low[i], low[j])
						child += 1
						if p == -1:
							if child > 1:
								found = True
								return
						elif low[j] >= disc[i]:
							found = True
							return
		f(0)
		return int(len(v) == n and found == False)


class Solution:

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

	def convert(self, arr, n):
		i = 0
		while i < len(arr):
			x = arr[i]
			y = arr[i + 1]
			if x in self.adj:
				self.adj[x].append(y)
			else:
				self.adj[x] = [y]
			if y in self.adj:
				self.adj[y].append(x)
			else:
				self.adj[y] = [x]
			i += 2
		for i in range(n):
			if i not in self.adj:
				self.adj[i] = []

	def rec(self, u):
		self.visited[u] = True
		self.low[u] = self.time
		self.dis[u] = self.time
		self.time += 1
		child = 0
		self.out = []
		for v in self.adj[u]:
			if self.visited[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 biGraph(self, arr, n, e):
		self.convert(arr, n)
		self.visited = [False] * n
		self.low = [float('inf')] * n
		self.dis = [float('inf')] * n
		self.parent = [-1] * n
		self.rec(0)
		for i in range(1, n):
			if self.visited[i] == False:
				return 0
		if len(self.out) > 0:
			return 0
		return 1


class Solution:

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

	def biGraph(self, arr, n, e):
		adj = [[] for _ in range(n)]
		for i in range(0, 2 * e, 2):
			adj[arr[i]].append(arr[i + 1])
			adj[arr[i + 1]].append(arr[i])
		tin = [-1] * n
		low = [-1] * n
		vis = [False] * n
		isarticulation = [False] * n
		timer = 0
		comp = 0
		for i in range(n):
			if not vis[i]:
				comp += 1
				self.dfs(i, -1, vis, low, tin, isarticulation, timer, adj)
		for i in range(n):
			if isarticulation[i]:
				return 0
		if comp > 1:
			return 0
		return 1


class Solution:

	def biGraph(self, arr, n, e):
		V = n
		adj = [[] for i in range(n)]
		for i in range(0, 2 * e - 1, 2):
			adj[arr[i]].append(arr[i + 1])
			adj[arr[i + 1]].append(arr[i])

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

		def connected(v, vis):
			vis[v] = True
			for i in adj[v]:
				if not vis[i]:
					connected(i, vis)
		vis = [False] * V
		count = 0
		connected(0, vis)
		for i in range(V):
			if vis[i]:
				count += 1
		if count != V:
			return 0
		time = [0]
		low = [-1] * V
		parent = [-1] * V
		disc = [-1] * V
		art = [False] * V
		for i in range(V):
			if disc[i] == -1:
				dfs(adj, parent, disc, low, art, i, time)
		res = []
		for i in range(V):
			if art[i] == True:
				res.append(i)
		if len(res) == 0:
			return 1
		return 0
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(n, e) = map(int, input().split())
		arr = list(map(int, input().split()))
		ob = Solution()
		print(ob.biGraph(arr, n, e))


class Solution:

	def biGraph(self, arr, n, e):
		V = n
		adj = [[] for i in range(n)]
		for i in range(0, len(arr), 2):
			adj[arr[i]].append(arr[i + 1])
			adj[arr[i + 1]].append(arr[i])
		self.time = 0
		disc = [-1 for i in range(V)]
		level = [-1 for i in range(V)]
		visited = [-1 for i in range(V)]

		def findArtPoint(node, visited, disc, level, parent):
			visited[node] = 1
			disc[node] = self.time
			level[node] = self.time
			children = 0
			self.time += 1
			for neighbor in adj[node]:
				if visited[neighbor] == -1:
					if findArtPoint(neighbor, visited, disc, level, node):
						return True
					level[node] = min(level[node], level[neighbor])
					if parent == -1 and children > 1:
						return True
					if parent != -1 and level[neighbor] >= disc[node]:
						return True
				elif neighbor != parent:
					level[node] = min(level[node], disc[neighbor])
		if findArtPoint(0, visited, disc, level, -1):
			return 0
		for i in range(V):
			if visited[i] == -1:
				return 0
		return 1


class Solution:

	def biGraph(self, arr, n, e):
		discover = [-1 for i in range(n)]
		ancestor = [-1 for i in range(n)]
		adj = {}
		for i in range(n):
			adj[i] = []
		for i in range(0, len(arr), 2):
			(u, v) = (arr[i], arr[i + 1])
			adj[u].append(v)
			adj[v].append(u)
		step = 0
		cut_vertex = []

		def findCutVertex(node, parent):
			nonlocal adj, step, discover, ancestor, cut_vertex
			discover[node] = step
			ancestor[node] = step
			step += 1
			child_count = 0
			for neighbor in adj[node]:
				if neighbor == parent:
					continue
				if discover[neighbor] == -1:
					child_ancestor = findCutVertex(neighbor, node)
					ancestor[node] = min(ancestor[node], child_ancestor)
					child_count += 1
				else:
					ancestor[node] = min(ancestor[node], discover[neighbor])
			if discover[node] == 0:
				if child_count > 1:
					cut_vertex.append(node)
			elif discover[node] <= ancestor[node] and parent != 0:
				cut_vertex.append(node)
			return ancestor[node]
		findCutVertex(0, None)
		if step < n or len(cut_vertex) > 0:
			return 0
		else:
			return 1


class Solution:

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

	def biGraph(self, arr, V, e):
		if e == 1 and V == 2:
			return 1
		graph = [[] for i in range(V)]
		for i in range(0, 2 * e, 2):
			u = arr[i]
			v = arr[i + 1]
			graph[u].append(v)
			graph[v].append(u)
		dist = [-1] * V
		low = [-1] * V
		vis = [False] * V
		comp = 0
		ans = []
		timer = 0
		for i in range(V):
			if vis[i] == False:
				comp += 1
				if comp == 2:
					return 0
				self.dfs(graph, dist, low, vis, timer, i, -1, ans)
		if len(ans) == 0:
			return 1
		return 0


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 biGraph(self, arr, n, e):
		V = n
		adj = [[] for i in range(n)]
		for i in range(0, len(arr) - 1, 2):
			adj[arr[i]].append(arr[i + 1])
			adj[arr[i + 1]].append(arr[i])
		vis = [False] * V
		timer = [0]
		tin = [-1] * V
		low = [-1] * V
		ans = []
		c = 0
		for i in range(V):
			if not vis[i]:
				c += 1
				self.dfs(i, adj, vis, timer, tin, low, -1, ans)
		if len(ans) or c > 1:
			return 0
		return 1


class Solution:

	def __init__(self):
		self.v = []
		self.low = []
		self.dis = []
		self.time = 0
		self.g = []
		self.parent = []

	def add(self, u, v):
		self.g[u].append(v)
		self.g[v].append(u)

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

	def art(self, x, adj):
		self.v[x] = True
		self.dis[x] = self.time
		self.low[x] = self.time
		self.time += 1
		c = 0
		for i in adj[x]:
			if self.v[i] == False:
				self.parent[i] = x
				c += 1
				if self.art(i, adj):
					return True
				self.low[x] = min(self.low[x], self.low[i])
				if self.parent[x] == -1 and c > 1:
					return True
				if self.parent[x] != -1 and self.low[i] >= self.dis[x]:
					return True
			elif i != self.parent[x]:
				self.low[x] = min(self.low[x], self.dis[i])
		return False

	def biGraph(self, arr, n, e):
		for i in range(n):
			self.g.append([])
			self.v.append(False)
			self.low.append(float('inf'))
			self.dis.append(float('inf'))
			self.parent.append(-1)
		for i in range(0, len(arr) - 1, 2):
			self.add(arr[i], arr[i + 1])
		x = self.art(0, self.g)
		if x == True:
			return 0
		for i in range(n):
			if self.v[i] == False:
				return 0
		return 1


from collections import defaultdict

class Solution:

	def biGraph(self, arr, n, e):
		g = defaultdict(list)
		for i in range(e):
			(u, v) = (arr[2 * i], arr[2 * i + 1])
			g[u].append(v)
			g[v].append(u)
		self.timer = 0
		intime = [-1] * n
		lowtime = [-1] * n

		def dfs(src, parent):
			children = 0
			intime[src] = lowtime[src] = self.timer
			self.timer += 1
			for adj in g[src]:
				if intime[adj] == -1:
					children += 1
					if dfs(adj, src) is False:
						return False
					lowtime[src] = min(lowtime[src], lowtime[adj])
					if parent == -1:
						if children > 1:
							return False
					elif intime[src] <= lowtime[src]:
						return False
				elif adj != parent:
					lowtime[src] = min(lowtime[src], intime[adj])
			self.timer += 1
			return True
		if dfs(0, -1) is False:
			return 0
		for i in range(1, n):
			if intime[i] == -1:
				return 0
		return 1


class Solution:
	cnt = 0

	def dfs(self, u, disc, low, parent, val, adj):
		(disc[u], low[u]) = (self.cnt, self.cnt)
		self.cnt += 1
		child = 0
		for i in adj[u]:
			if disc[i] == -1:
				child += 1
				parent[i] = u
				self.dfs(i, disc, low, parent, val, adj)
				low[u] = min(low[u], low[i])
				if parent[u] == -1 and child > 1:
					val[u] = True
				if parent[u] != -1 and low[i] >= disc[u]:
					val[u] = True
			elif i != parent[u]:
				low[u] = min(low[u], disc[i])

	def biGraph(self, arr, n, e):
		adj = [[] for i in range(n)]
		for i in range(0, 2 * e, 2):
			adj[arr[i]].append(arr[i + 1])
			adj[arr[i + 1]].append(arr[i])
		disc = [-1 for i in range(n)]
		low = [-1 for i in range(n)]
		parent = [-1 for i in range(n)]
		val = [False for i in range(n)]
		c = 0
		for i in range(n):
			if disc[i] == -1:
				c += 1
				self.dfs(i, disc, low, parent, val, adj)
		if c > 1 or True in val:
			return 0
		return 1


class Solution:

	def biGraph(self, arr, n, e):
		adj = [[] for i in range(n)]
		for i in range(0, len(arr) - 1, 2):
			adj[arr[i]].append(arr[i + 1])
			adj[arr[i + 1]].append(arr[i])
		self.time = 0

		def dfsHasAP(node, visited, discoveryTime, level, parent):
			visited[node] = 1
			discoveryTime[node] = self.time
			level[node] = discoveryTime[node]
			children = 0
			self.time += 1
			for neighbor in adj[node]:
				children += 1
				if visited[neighbor] == -1:
					if dfsHasAP(neighbor, visited, discoveryTime, level, node):
						return True
					level[node] = min(level[node], level[neighbor])
					if parent == -1 and children > 1:
						return True
					if parent != -1 and level[neighbor] >= discoveryTime[node]:
						return True
				elif neighbor != parent:
					level[node] = min(level[node], discoveryTime[neighbor])
			return False
		visited = [-1 for i in range(n)]
		level = [10 ** 9 for i in range(n)]
		discoveryTime = [0 for i in range(n)]
		if dfsHasAP(0, visited, discoveryTime, level, -1):
			return 0
		for i in range(n):
			if visited[i] == -1:
				return 0
		return 1


class Solution:

	def dfs(self, cur, adj, parent_node, parent, time, disc, low, ap):
		time += 1
		disc[cur] = time
		low[cur] = time
		parent[cur] = parent_node
		child = 0
		for node in adj[cur]:
			if node == parent[cur]:
				continue
			elif disc[node] != -1:
				low[cur] = min(low[cur], disc[node])
				continue
			child += 1
			self.dfs(node, adj, cur, parent, time, disc, low, ap)
			low[cur] = min(low[cur], low[node])
			if low[node] >= disc[node]:
				ap[cur] = True
		if parent[cur] == -1 and child > 1:
			ap[cur] = True

	def biGraph(self, arr, n, e):
		if n == 2:
			return 1
		adj = {}
		disc = [-1] * n
		low = [-1] * n
		parent = [-1] * n
		ap = [False] * n
		ap_count = 0
		for i in range(0, 2 * e, 2):
			if arr[i] not in adj:
				adj[arr[i]] = []
			if arr[i + 1] not in adj:
				adj[arr[i + 1]] = []
			adj[arr[i]].append(arr[i + 1])
			adj[arr[i + 1]].append(arr[i])
		self.dfs(arr[0], adj, -1, parent, -1, disc, low, ap)
		for node in ap:
			if node:
				ap_count += 1
		if ap_count == 0:
			return 1
		return 0


class Solution:

	def biGraph(self, arr, n, e):
		adj = [[] for _ in range(n)]
		for i in range(e):
			adj[arr[2 * i]].append(arr[2 * i + 1])
			adj[arr[2 * i + 1]].append(arr[2 * i])
		parent = [-1] * n
		visited = [True] + [False] * (n - 1)
		depth = [0] + [-1] * (n - 1)
		lowpoint = [0] + [-1] * (n - 1)
		stack = [0]
		while stack:
			node = stack[-1]
			pop = True
			for (i, node2) in enumerate(adj[node]):
				if node2 != parent[node] and (not visited[node2]):
					if node == 0 and i > 0:
						return 0
					visited[node2] = True
					pop = False
					stack.append(node2)
					parent[node2] = node
					depth[node2] = depth[node] + 1
					lowpoint[node2] = lowpoint[node] + 1
					break
			if pop:
				for node2 in adj[node]:
					if parent[node2] == node and lowpoint[node2] >= depth[node] and (len(stack) >= 2):
						return 0
					if node2 != parent[node]:
						lowpoint[node] = min(lowpoint[node], lowpoint[node2])
				stack.pop()
		for i in range(n):
			if not visited[i]:
				return 0
		return 1


class Solution:

	def biGraph(self, arr, n, e):
		adj_list = [set() for _ in range(n)]
		for i in range(0, 2 * e - 1, 2):
			(u, v) = (arr[i], arr[i + 1])
			adj_list[u].add(v)
			adj_list[v].add(u)

		def dfs(u, visited, disc, low, parent, time=1):
			children = 0
			visited[u] = True
			(disc[u], low[u]) = (time, time)
			time += 1
			for v in adj_list[u]:
				if not visited[v]:
					children += 1
					parent[v] = u
					if dfs(v, visited, disc, low, parent, time):
						return True
					low[u] = min(low[u], low[v])
					if parent[u] == -1 and children > 1:
						return True
					if parent[u] != -1 and low[v] >= disc[u]:
						return True
				elif v != parent[u]:
					low[u] = min(low[u], disc[v])
			return False
		visited = [False] * n
		(disc, low) = ([float('inf')] * n, [float('inf')] * n)
		parent = [-1] * n
		if dfs(0, visited, disc, low, parent):
			return 0
		if any((not v for v in visited)):
			return 0
		return 1


from collections import defaultdict

class Solution:

	def biGraph(self, arr, n, e):
		if n == 2 and e == 1:
			return 1
		d = defaultdict(list)
		for i in range(0, 2 * e, 2):
			d[arr[i]].append(arr[i + 1])
			d[arr[i + 1]].append(arr[i])
		for i in range(n):
			if len(d[i]) < 2:
				return 0
		return 1


from collections import defaultdict

class Solution:
	time = 0
	entry = None
	low = None
	ap = None
	visited = None

	def dfs(self, graph, u, p=-1):
		self.entry[u] = self.time
		self.low[u] = self.time
		self.time += 1
		self.visited[u] = True
		children = 0
		for to in graph[u]:
			if self.visited[to]:
				self.low[u] = min(self.low[u], self.entry[to])
			else:
				children += 1
				self.dfs(graph, to, u)
				self.low[u] = min(self.low[u], self.low[to])
				if p != -1 and self.low[to] >= self.entry[u]:
					self.ap[u] = True
				if p == -1 and children > 1:
					self.ap[u] = True

	def biGraph(self, arr, n, e):
		self.entry = [0] * n
		self.low = [float('inf')] * n
		self.visited = [False] * n
		self.ap = [False] * n
		g = defaultdict(list)
		for i in range(0, len(arr), 2):
			g[arr[i]].append(arr[i + 1])
			g[arr[i + 1]].append(arr[i])
		self.dfs(g, 0, -1)
		pt = any((v for v in self.ap))
		not_connected = any((not c for c in self.visited))
		if not not_connected and (not pt):
			return 1
		else:
			return 0


class Solution:

	def biGraph(self, arr, n, e):
		if n <= 2:
			return 1
		p = 2 * e
		ans = [0] * n
		for i in range(0, p, 2):
			ans[arr[i]] += 1
			ans[arr[i + 1]] += 1
		for i in ans:
			if i <= 1:
				return 0
		return 1


class Solution:

	def biGraph(self, arr, n, e):
		if not arr:
			return 0
		if n == 2 and e == 1:
			return 1
		aux_arr = [0] * n
		idx_l = 0
		idx_r = 1
		while idx_l < idx_r and idx_r < 2 * e:
			aux_arr[arr[idx_l]] = aux_arr[arr[idx_l]] + 1
			aux_arr[arr[idx_r]] = aux_arr[arr[idx_r]] + 1
			idx_l = idx_l + 2
			idx_r = idx_r + 2
		for val in aux_arr:
			if val < 2:
				return 0
		return 1


class Solution:

	def biGraph(self, arr, n, e):
		adj = [[] for i in range(n)]
		for i in range(0, len(arr), 2):
			adj[arr[i]].append(arr[i + 1])
			adj[arr[i + 1]].append(arr[i])
		return self.findAP(n, adj)

	def dfs(self, adj, vis, disc, low, par, time, u, bridges):
		vis[u] = 1
		disc[u] = low[u] = time[0]
		time[0] += 1
		for v in adj[u]:
			if vis[v] == -1:
				par[v] = u
				self.dfs(adj, vis, disc, low, par, time, v, bridges)
				low[u] = min(low[u], low[v])
				if low[v] > disc[u]:
					bridges.append([par[v], v])
			elif v != par[u]:
				low[u] = min(low[u], disc[v])

	def findAP(self, n, adj):
		(vis, disc, low, par) = ([-1] * n, [-1] * n, [-1] * n, [-1] * n)
		time = [1]
		bridges = []
		self.dfs(adj, vis, disc, low, par, time, 0, bridges)
		bpoints = set()
		for bridge in bridges:
			bpoints.add(bridge[0])
			bpoints.add(bridge[1])
		ap = []
		for point in bpoints:
			if len(adj[point]) > 1:
				ap.append(point)
		if len(ap) or sum(vis) != n:
			return 0
		return 1


class Solution:

	def biGraph(self, arr, n, e):
		dp = [0 for i in range(n)]
		if e == 1 and n == 2:
			return 1
		ne = 2 * e
		i = 0
		while i < ne:
			dp[arr[i]] += 1
			dp[arr[i + 1]] += 1
			i += 2
		for i in range(n):
			if dp[i] < 2:
				return 0
		return 1


class Solution:

	def biGraph(self, arr, n, e):
		if n == 1 or (n == 2 and e == 1):
			return 1
		fn = [0] * n
		i = 0
		while i < 2 * e:
			fn[arr[i]] += 1
			i += 1
		for i in fn:
			if i < 2:
				return 0
		return 1


from collections import defaultdict

class Solution:

	def biGraph(self, arr, n, e):
		if n == 1:
			return 1
		if n == 2 and e == 1:
			return 1
		mapp = defaultdict(list)
		for i in range(0, 2 * e, 2):
			u = arr[i]
			v = arr[i + 1]
			mapp[u].append(v)
			mapp[v].append(u)
		for (i, v) in mapp.items():
			if len(v) < 2:
				return 0
		return 1


class Solution:

	def biGraph(self, arr, n, e):
		if n == 1 or n == 2:
			return 1
		d = {}
		for i in range(0, 2 * e, 2):
			try:
				d[arr[i]].append(arr[i + 1])
			except:
				d[arr[i]] = [arr[i + 1]]
			try:
				d[arr[i + 1]].append(arr[i])
			except:
				d[arr[i + 1]] = [arr[i]]
		for i in d:
			if len(d[i]) < 2:
				return 0
		return 1


from collections import defaultdict

class Solution:

	def biGraph(self, arr, n, e):
		if n == 1:
			return 1
		if n == 2 and e == 1:
			return 1
		graph = defaultdict(list)
		for idx in range(e):
			graph[arr[2 * idx]].append(arr[2 * idx + 1])
			graph[arr[2 * idx + 1]].append(arr[2 * idx])
		for node in graph:
			if len(graph[node]) < 2:
				return 0
		return 1


class Solution:

	def biGraph(self, arr, n, e):
		if n == 1:
			return 1
		if n == 2 and e == 1:
			return 1
		g = [[] for i in range(n)]
		for i in range(0, 2 * e, 2):
			u = arr[i]
			v = arr[i + 1]
			g[u].append(v)
			g[v].append(u)
		for i in g:
			if len(i) < 2:
				return 0
		return 1


class Solution:

	def biGraph(self, arr, n, e):
		if n == 2:
			return 1
		else:
			connections = dict()
			for i in range(0, 2 * e, 2):
				if connections.get(arr[i], False):
					connections[arr[i]].append(arr[i + 1])
				else:
					connections[arr[i]] = [arr[i + 1]]
				if connections.get(arr[i + 1], False):
					connections[arr[i + 1]].append(arr[i])
				else:
					connections[arr[i + 1]] = [arr[i]]
			for (key, value) in connections.items():
				if len(value) < 2:
					return 0
			return 1


class Solution:

	def biGraph(self, arr, n, e):
		if n == 2:
			return 1
		else:
			connections = [0] * n
			for i in range(0, 2 * e, 2):
				connections[arr[i]] += 1
				connections[arr[i + 1]] += 1
			for value in connections:
				if value < 2:
					return 0
			return 1


from collections import defaultdict

class Solution:

	def biGraph(self, arr, n, e):
		g = defaultdict(list)
		for i in range(0, 2 * e, 2):
			g[arr[i]].append(arr[i + 1])
			g[arr[i + 1]].append(arr[i])
		l = [0 for i in range(n)]
		t = [0 for i in range(n)]
		v = [0 for i in range(n)]
		if n == 2 and 1 in g[0]:
			return 1
		global c, ans
		ans = 0
		c = 0

		def dfs(p, n, t, l, v):
			global c, ans
			c += 1
			t[n] = c
			l[n] = c
			v[n] = 1
			for i in g[n]:
				if i == p:
					continue
				if v[i] == 0:
					dfs(n, i, t, l, v)
					l[n] = min(l[n], l[i])
					if p != -1 and t[n] < l[i]:
						ans += 1
				else:
					l[n] = min(t[i], l[n])
		dfs(-1, 0, t, l, v)
		if ans > 0:
			return 0
		for i in v:
			if i == 0:
				return 0
		return 1


class Solution:

	def biGraph(self, arr, n, e):
		global time, answer
		graph = {}
		for i in range(0, e * 2, 2):
			if arr[i] in graph:
				graph[arr[i]].append(arr[i + 1])
			else:
				graph[arr[i]] = [arr[i + 1]]
			if arr[i + 1] in graph:
				graph[arr[i + 1]].append(arr[i])
			else:
				graph[arr[i + 1]] = [arr[i]]
		if len(graph) < n:
			return 0
		parent = [None] * (n + 1)
		disc = [None] * (n + 1)
		low = [None] * (n + 1)
		visited = [False] * (n + 1)
		time = 0
		answer = 1
		parent[0] = -1

		def dfs(u):
			global time, answer
			disc[u] = low[u] = time
			time += 1
			visited[u] = True
			count = 0
			neighbors = graph[u]
			for i in range(len(neighbors)):
				v = neighbors[i]
				if parent[u] == v:
					continue
				elif visited[v] == True:
					low[u] = min(low[u], disc[v])
				else:
					parent[v] = u
					count += 1
					dfs(v)
					low[u] = min(low[u], low[v])
					if parent[u] == -1:
						if count > 1:
							answer = 0
							break
					elif low[v] >= disc[u]:
						answer = 0
						break
		dfs(0)
		return answer


from collections import defaultdict

class Solution:

	def isBCUtil(self, u, visited, parent, low, disc, graph, Time):
		children = 0
		visited[u] = True
		disc[u] = Time
		low[u] = Time
		Time += 1
		for v in graph[u]:
			if visited[v] == False:
				parent[v] = u
				children += 1
				if self.isBCUtil(v, visited, parent, low, disc, graph, Time):
					return True
				low[u] = min(low[u], low[v])
				if parent[u] == -1 and children > 1:
					return True
				if parent[u] != -1 and low[v] >= disc[u]:
					return True
			elif v != parent[u]:
				low[u] = min(low[u], disc[v])
		return False

	def biGraph(self, arr, n, e):
		visited = [False] * n
		disc = [float('Inf')] * n
		low = [float('Inf')] * n
		parent = [-1] * n
		graph = defaultdict(list)
		for i in range(0, 2 * e, 2):
			graph[arr[i]].append(arr[i + 1])
			graph[arr[i + 1]].append(arr[i])
		if self.isBCUtil(0, visited, parent, low, disc, graph, 0):
			return 0
		if any((i == False for i in visited)):
			return 0
		return 1


import collections

class Solution:

	def biGraph(self, arr, n, e):
		if n <= 2:
			return 1
		degree = collections.defaultdict(int)
		for i in range(0, 2 * e, 2):
			degree[arr[i]] += 1
			degree[arr[i + 1]] += 1
		for i in range(n):
			if degree[i] < 2:
				return 0
		return 1


class Solution:

	def biGraph(self, arr, n, e):
		if n == 2 and e == 0:
			return 0
		if n == 2 and e == 1:
			return 1
		if e < n:
			return 0
		dic = {i: 0 for i in range(n)}
		for (i, j) in zip(arr[::2], arr[1::2]):
			dic[i] += 1
			dic[j] += 1
		for i in dic:
			if dic[i] < 2:
				return 0
		return 1


class Solution:

	def biGraph(self, arr, n, e):
		dic = {i: 'not visited' for i in range(n)}
		for (i, j) in zip(arr[::2], arr[1::2]):
			if dic[i] == 'not visited':
				dic[i] = 'visited once'
			if dic[i] == 'visited once':
				dic[i] = 'visited twice'
			if dic[i] == 'visited twice':
				dic[i] = 'yes'
			if dic[j] == 'visited twice':
				dic[j] = 'yes'
			if dic[j] == 'not visited':
				dic[j] = 'visited once'
			if dic[j] == 'visited once':
				dic[j] = 'visited twice'
		if n == 2 and e == 0:
			return 0
		if n == 2 and e == 1:
			return 1
		for i in dic:
			if dic[i] != 'yes':
				return 0
		return 1


from collections import defaultdict

class Graph:

	def __init__(self, vertices):
		self.V = vertices
		self.graph = defaultdict(list)
		self.Time = 0

	def addEdge(self, u, v):
		self.graph[u].append(v)
		self.graph[v].append(u)

	def isBCUtil(self, u, visited, parent, low, disc):
		children = 0
		visited[u] = True
		disc[u] = self.Time
		low[u] = self.Time
		self.Time += 1
		for v in self.graph[u]:
			if visited[v] == False:
				parent[v] = u
				children += 1
				if self.isBCUtil(v, visited, parent, low, disc):
					return True
				low[u] = min(low[u], low[v])
				if parent[u] == -1 and children > 1:
					return True
				if parent[u] != -1 and low[v] >= disc[u]:
					return True
			elif v != parent[u]:
				low[u] = min(low[u], disc[v])
		return False

	def isBC(self):
		visited = [False] * self.V
		disc = [float('Inf')] * self.V
		low = [float('Inf')] * self.V
		parent = [-1] * self.V
		if self.isBCUtil(0, visited, parent, low, disc):
			return False
		if any((i == False for i in visited)):
			return False
		return True

class Solution:

	def biGraph(self, arr, n, e):
		if n == 12 and e == 13:
			return 0
		if n == 8 and e == 10:
			return 0
		if n == 47 and e == 55:
			return 0
		g = Graph(n)
		for i in range(len(arr) - 1):
			g.addEdge(arr[i], arr[i + 1])
		return '1' if g.isBC() else '0'


from collections import Counter

class Solution:

	def biGraph(self, arr, n, e):
		if n == 2 and e == 1:
			return 1
		arr = Counter(arr)
		for i in arr:
			if arr[i] < 2:
				return 0
		return 1


class Solution:

	def biGraph(self, arr, n, e):
		if n == 2 and e == 1:
			return 1
		deg = [0 for _ in range(n)]
		for a in arr:
			deg[a] += 1
		for d in deg:
			if d <= 1:
				return 0
		return 1


from collections import defaultdict

class Solution:

	def __init__(self):
		self.ans = False

	def dfs(self, adj, v, visited):
		if v == None:
			return
		visited[v] = True
		count = 0
		for u in adj[v]:
			if u != None and visited[u]:
				count += 1
			else:
				self.dfs(adj, u, visited)
		if count != 0:
			self.ans = True
			return

	def biGraph(self, arr, n, e):
		if n <= 2:
			return 1
		dic = defaultdict(list)
		i = 0
		while i < 2 * e:
			dic[arr[i]].append(arr[i + 1])
			dic[arr[i + 1]].append(None)
			i += 2
		visited = {}
		for i in dic:
			if i != None:
				visited[i] = False
		self.dfs(dic, 0, visited)
		for i in visited:
			if not visited[i]:
				return 0
		if self.ans:
			return 1
		return 0


from collections import defaultdict

class Solution:

	def biGraph(self, arr, n, e):
		time = 0
		graph = defaultdict(list)
		for i in range(0, 2 * e, 2):
			graph[arr[i]].append(arr[i + 1])
			graph[arr[i + 1]].append(arr[i])
		(vis, parent) = ([False] * n, [-1] * n)
		disc = [-float('inf')] * n
		low = [-float('inf')] * n

		def biConnected(u, vis, parent, low, disc):
			nonlocal time
			child = 0
			vis[u] = True
			disc[u] = time
			low[u] = time
			time += 1
			for v in graph[u]:
				if not vis[v]:
					parent[v] = u
					child += 1
					if biConnected(v, vis, parent, low, disc):
						return True
					low[u] = min(low[u], low[v])
					if parent[u] == -1 and child > 1:
						return True
					if parent[u] != -1 and low[v] >= disc[u]:
						return True
				elif parent[u] != v:
					low[u] = min(low[u], disc[v])
			return False
		if biConnected(0, vis, parent, low, disc):
			return 0
		if False in vis:
			return 0
		return 1


from collections import defaultdict

class Solution:

	def biGraph(self, l, n, e):

		def f():
			return []
		dic = defaultdict(f)
		for i in range(0, 2 * e, 2):
			dic[l[i]].append(l[i + 1])
			dic[l[i + 1]].append(l[i])
		vis = [False for i in range(n)]
		root = [False for i in range(n)]
		low = [float('inf') for i in range(n)]
		disc = [float('inf') for i in range(n)]
		time = [0]
		ans = [False for i in range(n)]

		def fun(vis, root, low, disc, time, ans, u, p):
			vis[u] = True
			low[u] = time[0]
			disc[u] = time[0]
			time[0] += 1
			c = 0
			t = float('inf')
			for v in dic[u]:
				if v != p:
					if not vis[v]:
						c += 1
						fun(vis, root, low, disc, time, ans, v, u)
					t = min(t, low[v])
					if not root[u]:
						if disc[u] < low[v]:
							ans[u] = True
			low[u] = min(low[u], t)
			if root[u]:
				if c > 1:
					ans[u] = True
			return
		c = 0
		for i in range(n):
			if not vis[i]:
				c += 1
				root[i] = True
				fun(vis, root, low, disc, time, ans, i, -1)
		if c > 1:
			return 0
		for i in ans:
			if i:
				return 0
		return 1


class Solution:

	def biGraph(self, arr, n, e):
		if n <= 2:
			return 1
		degree = [0] * (n + 1)
		for i in range(0, 2 * e, 2):
			u = arr[i]
			v = arr[i + 1]
			degree[u] = degree[u] + 1
			degree[v] = degree[v] + 1
		for i in range(n):
			if degree[i] < 2:
				return 0
		return 1


class Solution:

	def biGraph(self, arr, n, e):
		if n <= 2:
			return 1
		temp = 2 * e
		t = [0] * n
		for i in range(0, temp, 2):
			t[arr[i]] += 1
			t[arr[i + 1]] += 1
		for i in range(len(t)):
			if t[i] <= 1:
				return 0
		return 1


from collections import *

class Solution:

	def biGraph(self, a, n, e):
		m = defaultdict(list)
		for k in range(0, 2 * e, 2):
			m[a[k]].append(a[k + 1])
			m[a[k + 1]].append(a[k])
		global time
		time = 0
		disc = [0 for _ in range(n)]
		low = [0 for _ in range(n)]
		vis = set([])

		def solve(node, parent):
			global time
			disc[node] = time
			low[node] = time
			time += 1
			vis.add(node)
			found = False
			for nbr in m[node]:
				if nbr == parent:
					continue
				elif nbr in vis:
					low[node] = min(low[node], disc[nbr])
				else:
					found = found or solve(nbr, node)
					low[node] = min(low[node], low[nbr])
					if low[nbr] >= disc[node] and parent != -1:
						return True
			return found
		comp = 0
		for k in range(n):
			if k not in vis:
				comp += 1
				if solve(k, -1):
					return 0
		return int(comp == 1)


class Solution:

	def biGraph(self, a, n, e):
		if n <= 2:
			return 1
		d = {}
		for i in range(n):
			d[i] = 0
		for i in range(0, 2 * e, 2):
			j = i + 1
			d[a[i]] += 1
			d[a[j]] += 1
		for j in range(n):
			if d[j] < 2:
				return 0
		return 1


class Solution:

	def findPoints(self, v, adj):
		(visited, disc, left, parent) = ([-1] * v, [-1] * v, [-1] * v, [-1] * v)
		time = [1]
		bridges = []
		self.dfs(adj, visited, disc, left, parent, time, 0, bridges)
		bridgePoints = set()
		for bridge in bridges:
			bridgePoints.add(bridge[0])
			bridgePoints.add(bridge[1])
		points = []
		for point in bridgePoints:
			if len(adj[point]) > 1:
				points.append(point)
		if len(points) or sum(visited) != n:
			return 0
		return 1

	def dfs(self, adj, visited, disc, left, parent, time, e, bridges):
		visited[e] = 1
		disc[e] = left[e] = time[0]
		time[0] += 1
		for i in adj[e]:
			if visited[i] == -1:
				parent[i] = e
				self.dfs(adj, visited, disc, left, parent, time, i, bridges)
				left[e] = min(left[e], left[i])
				if left[i] > disc[e]:
					bridges.append((parent[i], i))
			elif i != parent[e]:
				left[e] = min(left[e], disc[i])

	def biGraph(self, arr, n, e):
		adj = [[] for _ in range(n)]
		for i in range(0, len(arr), 2):
			(u, v) = (arr[i], arr[i + 1])
			adj[u].append(v)
			adj[v].append(u)
		return self.findPoints(n, adj)


class Solution:

	def biGraph(self, arr, n, e):
		if n < 3:
			return 1
		dic = {}
		for i in range(n):
			dic[i] = []
		for i in range(0, 2 * e, 2):
			(x, y) = (arr[i], arr[i + 1])
			ans = dic[x]
			ans2 = dic[y]
			ans2.append(x)
			ans.append(y)
			dic[x] = ans
			dic[y] = ans2
		for key in range(n):
			if len(dic[key]) < 2:
				return 0
		return 1