You have n binary tree nodes numbered from 0 to n - 1 where node i has two children leftChild[i] and rightChild[i], return true if and only if all the given nodes form exactly one valid binary tree.
If node i has no left child then leftChild[i] will equal -1, similarly for the right child.
Note that the nodes have no values and that we only use the node numbers in this problem.
 
Example 1:

Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]
Output: true

Example 2:

Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,3,-1,-1]
Output: false

Example 3:

Input: n = 2, leftChild = [1,0], rightChild = [-1,-1]
Output: false

Example 4:

Input: n = 6, leftChild = [1,-1,-1,4,-1,-1], rightChild = [2,-1,-1,5,-1,-1]
Output: false

 
Constraints:

1 <= n <= 10^4
leftChild.length == rightChild.length == n
-1 <= leftChild[i], rightChild[i] <= n - 1

Difficulty: MEDIUM
Tags: Tree algorithms

Graph algorithms

Graph traversal

Spanning trees

Starter code:
class Solution:
    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
        

Solutions:
class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		(leftset, rightset) = (set(leftChild), set(rightChild))
		roots = []
		for i in range(n):
			if i not in leftset and i not in rightset:
				roots.append(i)
				if len(roots) > 1:
					return False
		if not roots:
			return False
		root = roots[0]
		nodes = []

		def dfs(root):
			if root == -1:
				return
			if len(nodes) > n:
				return
			nodes.append(root)
			dfs(leftChild[root])
			dfs(rightChild[root])
		dfs(root)
		return len(nodes) == n


class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		root = set(range(n))
		for c in leftChild + rightChild:
			if c == -1:
				continue
			if c not in root:
				return False
			root.remove(c)
		if len(root) != 1:
			return False

		def dfs(node):
			if node == -1:
				return 0
			return 1 + dfs(leftChild[node]) + dfs(rightChild[node])
		return dfs(root.pop()) == n


class Solution:

	def validateBinaryTreeNodes(self, n: int, left_children: List[int], right_children: List[int]) -> bool:
		root = self.find_root(n, left_children, right_children)
		if root == -1:
			return False
		return self.helper(root, n, left_children, right_children)

	def find_root(self, n, left_children, right_children):
		left_counter = collections.Counter(left_children)
		right_counter = collections.Counter(right_children)
		for i in range(n):
			if i not in left_counter and i not in right_counter:
				return i
		return -1

	def helper(self, root, n, left_children, right_children):
		visited = set()
		if not self.dfs(root, left_children, right_children, visited):
			return False
		return len(visited) == n

	def dfs(self, root, left_children, right_children, visited):
		if root == -1:
			return True
		if root in visited:
			return False
		visited.add(root)
		left = self.dfs(left_children[root], left_children, right_children, visited)
		right = self.dfs(right_children[root], left_children, right_children, visited)
		return left and right


class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		parents = [(idx, 0) for idx in range(n)]

		def find(idx):
			original_idx = idx
			height = 0
			while parents[idx][0] != idx:
				height += 1
				idx = parents[idx][0]
			parents[original_idx] = (idx, 0)
			return parents[idx]

		def union(idx1, idx2):
			(parent1, rank1) = find(idx1)
			(parent2, rank2) = find(idx2)
			if parent1 == parent2:
				return False
			if rank1 > rank2:
				parents[parent2] = (parent1, rank1)
			elif rank2 > rank1:
				parents[parent1] = (parent2, rank2)
			else:
				parents[parent1] = (parent2, rank2 + 1)
			return True
		for (idx1, idx2) in enumerate(leftChild):
			if idx2 == -1:
				continue
			if not union(idx1, idx2):
				return False
		for (idx1, idx2) in enumerate(rightChild):
			if idx2 == -1:
				continue
			if not union(idx1, idx2):
				return False
		(group, _) = find(0)
		for idx in range(n):
			if find(idx)[0] != group:
				return False
		return True


class Solution:

	def validateBinaryTreeNodes(self, n: int, left: List[int], right: List[int]) -> bool:
		children = {}
		nodes = {}
		for i in range(n):
			(l, r) = (left[i], right[i])
			if l != -1 and l in children or (r != -1 and r in children):
				print('Here Yo-', children, l, r)
				return False
			elif i in children and children[i] in [l, r]:
				print('Baap ko gali')
				return False
			elif i in [l, r]:
				print('Selfie')
				return False
			nodes[i] = [l, r]
			children[l] = i
			children[r] = i
		root = 0
		for i in range(n):
			if i not in children:
				root = i
				break
		count = 0
		frontier = [root]
		seen = set()
		while frontier:
			cur = frontier.pop()
			if cur == -1:
				continue
			count += 1
			c = nodes[cur]
			if c[0] != -1 and c[0] in seen or (c[1] != -1 and c[1] in seen):
				return False
			if c[0] != -1:
				seen.add(c[0])
				frontier.append(c[0])
			if c[1] != -1:
				seen.add(c[1])
				frontier.append(c[1])
		if count != n:
			return False
		return True


from functools import reduce

class Solution:

	def validateBinaryTreeNodes(self, n, leftChild, rightChild) -> bool:
		g = dict(enumerate(zip(leftChild, rightChild)))
		root = set(range(n)) - reduce(set.union, list(map(set, [leftChild, rightChild])))
		if len(root) != 1:
			return False
		root = next(iter(root))

		def dfs(n):
			if n == -1:
				return True
			if n not in g:
				return False
			return all(map(dfs, g.pop(n)))
		out = dfs(root)
		return out and (not g)


class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		indegree = [0] * n
		for i in leftChild:
			if i >= 0:
				indegree[i] += 1
		for i in rightChild:
			if i >= 0:
				indegree[i] += 1
		root = -1
		for (i, d) in enumerate(indegree):
			if d == 0:
				root = i
				break
		if root < 0:
			return False
		visited = [False] * n
		res = True

		def dfs(node):
			if visited[node]:
				nonlocal res
				res = False
				return
			visited[node] = True
			if leftChild[node] >= 0:
				dfs(leftChild[node])
			if rightChild[node] >= 0:
				dfs(rightChild[node])
		dfs(root)
		for node in range(n):
			if not visited[node]:
				res = False
		return res


import collections

class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		if n == 1:
			return True
		degree = [0] * n
		graph = []
		for _ in range(n):
			graph.append(set())
		for (i, v) in enumerate(leftChild):
			if v != -1:
				degree[v] += 1
				graph[i].add(v)
		for (i, v) in enumerate(rightChild):
			if v != -1:
				degree[v] += 1
				graph[i].add(v)
		root = [i for i in range(n) if degree[i] == 0]
		if len(root) != 1:
			return False
		visited = set()
		self.dfs(root[0], graph, visited)
		if len(visited) != n:
			return False
		counter = collections.Counter(degree)
		return len(counter) == 2 and counter[0] == 1 and (counter[1] == n - 1)

	def dfs(self, idx, graph, visited):
		visited.add(idx)
		for j in graph[idx]:
			if j not in visited:
				self.dfs(j, graph, visited)


class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:

		def cycle(node):
			if seen[node] == 1:
				return True
			if seen[node] == 2:
				return False
			seen[node] = 1
			for nei in g[node]:
				if cycle(nei):
					return True
			seen[node] = 2
			return False
		indeg = [0] * n
		g = [[] for _ in range(n)]
		for (i, (u, v)) in enumerate(zip(leftChild, rightChild)):
			if u > -1:
				g[i].append(u)
				indeg[u] += 1
			if v > -1:
				g[i].append(v)
				indeg[v] += 1
		counts = Counter(indeg)
		if counts[0] > 1 or counts[0] == 0:
			return False
		if any((count > 1 for count in list(counts.keys()))):
			return False
		root = indeg.index(0)
		seen = [0] * n
		return not cycle(root) and all((seen[node] == 2 for node in range(n)))


class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:

		def method1():

			def dfs(node):
				if node >= n:
					return False
				if node in seen:
					return False
				seen.add(node)
				L = True
				if leftChild[node] != -1:
					L = dfs(leftChild[node])
				R = True
				if rightChild[node] != -1:
					R = dfs(rightChild[node])
				return L and R
			seen = set()
			valid = dfs(0)
			print(len(seen), valid)
			return valid and len(seen) == n

		def method2():
			indeg = collections.defaultdict(int)
			for i in range(n):
				if leftChild[i] != -1:
					indeg[leftChild[i]] += 1
				if rightChild[i] != -1:
					indeg[rightChild[i]] += 1
			root = 0
			for i in range(n):
				if indeg[i] == 0:
					root = i

			def dfs(node):
				if node >= n:
					return False
				if node in seen:
					return False
				seen.add(node)
				L = True
				if leftChild[node] != -1:
					L = dfs(leftChild[node])
				R = True
				if rightChild[node] != -1:
					R = dfs(rightChild[node])
				return L and R
			seen = set()
			valid = dfs(root)
			print(len(seen), valid)
			return valid and len(seen) == n
		return method2()


class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:

		def union(origin, destination, parents, rank):
			parent_origin = find(origin, parents)
			parent_destination = find(destination, parents)
			if parent_origin == parent_destination:
				return False
			if rank[parent_origin] < rank[parent_destination]:
				parents[parent_origin] = parents[parent_destination]
			else:
				parents[parent_destination] = parents[parent_origin]
				if rank[parent_origin] == rank[parent_destination]:
					rank[parent_origin] += 1
			return True

		def find(x, parents):
			if parents[x] == x:
				return parents[x]
			return find(parents[x], parents)
		parents = [n for n in range(n)]
		rank = [0 for _ in range(n)]
		for (i, (left, right)) in enumerate(zip(leftChild, rightChild)):
			if left != -1:
				if not union(i, left, parents, rank):
					return False
			if right != -1:
				if not union(i, right, parents, rank):
					return False
		return len({find(x, parents) for x in range(n)}) == 1


from itertools import chain

class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		s = set(range(n))
		for c in chain(leftChild, rightChild):
			if c != -1:
				if c not in s:
					return False
				s.remove(c)
		if len(s) != 1:
			return

		def dfs(node: int):
			if node == -1:
				return
			nonlocal n
			n -= 1
			dfs(leftChild[node])
			dfs(rightChild[node])
		dfs(s.pop())
		return n == 0


class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		parent = {}
		for i in range(n):
			if leftChild[i] != -1:
				if leftChild[i] in parent:
					return False
				parent[leftChild[i]] = i
			if rightChild[i] != -1:
				if rightChild[i] in parent:
					return False
				parent[rightChild[i]] = i
		if len(parent) != n - 1:
			return False
		f = {}

		def find(x):
			f.setdefault(x, x)
			if f[x] != x:
				f[x] = find(f[x])
			return f[x]

		def union(x, y):
			f[find(x)] = find(y)
		for x in parent:
			union(x, parent[x])
		return len(set([find(x) for x in range(n)])) == 1


class Solution:

	def validateBinaryTreeNodes(self, nodes: int, leftChild: List[int], rightChild: List[int]) -> bool:
		num_edges = 0
		graph = collections.defaultdict(list)
		indegree = {i: 0 for i in range(nodes)}
		parents = {i: None for i in range(nodes)}
		for (n, (l, r)) in enumerate(zip(leftChild, rightChild)):
			if l != -1:
				num_edges += 1
				graph[n].append(l)
				if parents[l] is not None or parents[n] == l:
					return False
				parents[l] = n
				indegree[l] += 1
			if r != -1:
				num_edges += 1
				graph[n].append(r)
				if parents[r] is not None or parents[n] == r:
					return False
				parents[r] = n
				indegree[r] += 1
		if num_edges != nodes - 1:
			return False
		roots = [i for i in range(len(parents)) if parents[i] is None]
		if len(roots) != 1:
			return False
		root = roots[0]
		return max(leftChild[root], rightChild[root]) != -1 or nodes == 1


class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		edge = [[] for i in range(n)]
		cntEdge = 0
		for (u, v) in enumerate(leftChild):
			if v == -1:
				continue
			else:
				edge[u].append(v)
				edge[v].append(u)
				cntEdge += 1
		for (u, v) in enumerate(rightChild):
			if v == -1:
				continue
			else:
				edge[u].append(v)
				edge[v].append(u)
				cntEdge += 1
		if cntEdge != n - 1:
			return False
		vis = [False for i in range(n)]
		stack = []
		stack.append(0)
		while stack:
			u = stack.pop()
			vis[u] = True
			for v in edge[u]:
				if not vis[v]:
					stack.append(v)
		return all(vis)


class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		visited = [False] * n
		cycle = False

		def dfs(root):
			nonlocal cycle
			if root == -1:
				return
			if not visited[root]:
				visited[root] = True
				dfs(leftChild[root])
				dfs(rightChild[root])
			else:
				cycle = True

		def find_root():
			in_degree = {}
			for i in range(n):
				in_degree[i] = 0
			in_degree[-1] = 0
			for i in range(n):
				in_degree[leftChild[i]] += 1
				in_degree[rightChild[i]] += 1
			has_seen = False
			root = None
			print(in_degree)
			for (k, v) in list(in_degree.items()):
				if v == 0:
					if has_seen:
						return None
					root = k
					has_seen = True
			return root
		root = find_root()
		print(root)
		if root == None:
			return False
		dfs(root)
		if cycle:
			return False
		return all(visited)


def build_graph(n, leftChild, rightChild):
	adj_list = [[] for _ in range(n)]
	for i in range(len(leftChild)):
		left = leftChild[i]
		right = rightChild[i]
		if left != -1:
			adj_list[i].append(left)
		if right != -1:
			adj_list[i].append(right)
	return adj_list

def gather_inDegrees(n, graph):
	inDegrees = [0] * n
	for i in range(len(graph)):
		for neighbor in graph[i]:
			inDegrees[neighbor] += 1
	return inDegrees

class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		graph = build_graph(n, leftChild, rightChild)
		inDegrees = gather_inDegrees(n, graph)
		print(inDegrees)
		zero_count = 0
		for count in inDegrees:
			if count > 1:
				return False
			if count == 0:
				if zero_count == 1:
					return False
				else:
					zero_count += 1
		visited = set()
		topo_order = []
		processing = set()

		def _dfs(node):
			processing.add(node)
			visited.add(node)
			neighbors = graph[node]
			for neighbor in neighbors:
				if neighbor in visited and neighbor in processing:
					return True
				elif neighbor not in visited:
					if _dfs(neighbor):
						return True
			processing.remove(node)
			topo_order.append(node)
			return False
		for i in range(n):
			if i not in visited:
				if _dfs(i):
					return False
		return True


class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		dic = collections.defaultdict(list)
		for (idx, (left, right)) in enumerate(zip(leftChild, rightChild)):
			if left != -1:
				dic[left].append(idx)
			if right != -1:
				dic[right].append(idx)
		parent = set()
		for (key, value) in dic.items():
			if len(value) > 1:
				return False
			if [key] == dic.get(value[0], []):
				return False
			parent.add(value[0])
		if parent and len(dic.keys() - parent) == 0:
			return False
		return len(dic) == n - 1


class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		graph = [set() for _ in range(n)]
		degree = [0] * n
		for i in range(n):
			if leftChild[i] != -1:
				graph[i].add(leftChild[i])
				degree[leftChild[i]] += 1
			if rightChild[i] != -1:
				graph[i].add(rightChild[i])
				degree[rightChild[i]] += 1
		q = collections.deque()
		for i in range(n):
			if degree[i] == 0:
				q.append(i)
			if degree[i] > 1:
				return False
		if len(q) > 1 or len(q) == 0:
			return False
		visited = set()
		while q:
			node = q.pop()
			visited.add(node)
			for neigh in graph[node]:
				if neigh in visited:
					return False
				degree[neigh] -= 1
				if degree[neigh] == 0:
					q.append(neigh)
		return len(visited) == n


class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		visited = [0 for _ in range(n)]
		from collections import deque
		for i in range(n):
			if visited[i] == 1:
				continue
			q = deque()
			q.append(i)
			visited[i] = 1
			while q:
				cur = q.popleft()
				left = leftChild[cur]
				right = rightChild[cur]
				if left != -1:
					if visited[left] == 1:
						return False
					else:
						visited[left] = 1
						q.append(left)
				if right != -1:
					if visited[right] == 1:
						return False
					else:
						visited[right] = 1
						q.append(right)
			visited[i] = 0
			leftChild[i] = -1
			rightChild[i] = -1
		return n - sum(visited) == 1


class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		tree = {}
		notroots = set()
		for i in range(n):
			tree[i] = []
			left = leftChild[i]
			right = rightChild[i]
			if left != -1:
				notroots.add(left)
				tree[i].append(left)
			if right != -1:
				notroots.add(right)
				tree[i].append(right)
		if len(notroots) == n:
			return False

		def helper(node):
			if node not in tree:
				path.add(node)
				return True
			if node in path:
				return False
			path.add(node)
			children = tree[node]
			nchild = len(children)
			for i in range(nchild):
				child = children[i]
				if not helper(child):
					return False
			return True
		path = set()
		for i in range(n):
			if i not in notroots:
				if not helper(i):
					return False
				break
		for i in range(n):
			if i not in path:
				return False
		return True


class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		indegree = [0 for i in range(n)]
		for i in range(len(leftChild)):
			if leftChild[i] != -1:
				indegree[leftChild[i]] += 1
				if indegree[leftChild[i]] > 1:
					return False
			if rightChild[i] != -1:
				indegree[rightChild[i]] += 1
				if indegree[rightChild[i]] > 1:
					return False
		root = -1
		for node in range(len(indegree)):
			if indegree[node] == 0:
				if root == -1:
					root = node
				else:
					return False
		if root == -1:
			return False

		def countNodes(root, l, r):
			if root is -1:
				return 0
			return 1 + countNodes(l[root], l, r) + countNodes(r[root], l, r)
		return countNodes(root, leftChild, rightChild) == n


class DSU:

	def __init__(self, n):
		self.parent = list(range(n))
		self.size = [1] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, x, y):
		(xp, yp) = (self.find(x), self.find(y))
		if xp == yp:
			return False
		if self.size[xp] < self.size[yp]:
			(xp, yp) = (yp, xp)
		self.size[xp] += self.size[yp]
		self.parent[yp] = xp
		return True

class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		dsu = DSU(n)
		for i in range(n):
			if leftChild[i] >= 0 and (not dsu.union(i, leftChild[i])):
				return False
			if rightChild[i] >= 0 and (not dsu.union(i, rightChild[i])):
				return False
		p = dsu.find(0)
		for i in range(n):
			if p != dsu.find(i):
				return False
		return True


class DSU:

	def __init__(self, count):
		self.components = count
		self.parent = [i for i in range(count)]
		self.size = [1 for _ in range(count)]

	def find(self, x):
		root = x
		while root != self.parent[root]:
			root = self.parent[root]
		while root != x:
			next_root = self.parent[x]
			self.parent[x] = root
			x = next_root
		return root

	def union(self, x, y):
		(r1, r2) = (self.find(x), self.find(y))
		if r1 == r2:
			return False
		if self.size[r1] < self.size[r2]:
			self.size[r2] += self.size[r1]
			self.parent[r1] = r2
		else:
			self.size[r1] += self.size[r2]
			self.parent[r2] = r1
		self.components -= 1
		return True

class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		dsu = DSU(n)
		for (i, left) in enumerate(leftChild):
			if left != -1:
				if not dsu.union(i, left):
					return False
		for (i, right) in enumerate(rightChild):
			if right != -1:
				if not dsu.union(i, right):
					return False
		return dsu.components == 1


class dsu:

	def __init__(self, n):
		self.parent = list(range(n))
		self.count = n

	def find(self, x):
		if self.parent[x] != x:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, x, y):
		(px, py) = (self.find(x), self.find(y))
		if px == py:
			return False
		if px != py:
			self.count = self.count - 1
			self.parent[px] = py
			return True

class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		DSU = dsu(n)
		indegree = [0] * n
		for i in range(n):
			if leftChild[i] != -1:
				indegree[leftChild[i]] += 1
			if rightChild[i] != -1:
				indegree[rightChild[i]] += 1
		count_zeroes = 0
		for i in indegree:
			if i == 0:
				count_zeroes += 1
			if count_zeroes > 1:
				return False
		for (node, child) in enumerate(zip(leftChild, rightChild)):
			if child[0] != -1:
				if DSU.union(node, child[0]) == False:
					return False
			if child[1] != -1:
				if DSU.union(node, child[1]) == False:
					return False
		return True


class DSU:

	def __init__(self, n):
		self.n = n
		self.parent = [x for x in range(n)]
		self.rank = [0 for x in range(n)]

	def find(self, x):
		if self.parent[x] != x:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, s, t):
		(sp, tp) = (self.find(s), self.find(t))
		if sp == tp:
			return False
		if self.rank[sp] > self.rank[tp]:
			self.parent[tp] = sp
		elif self.rank[sp] < self.rank[tp]:
			self.parent[sp] = tp
		else:
			self.parent[sp] = tp
			self.rank[tp] += 1
		return True

class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		edges = set()
		net = DSU(n)
		for idx in range(n):
			if leftChild[idx] != -1:
				leftEdge = (min(idx, leftChild[idx]), max(idx, leftChild[idx]))
				if leftEdge in edges:
					return False
				edges.add(leftEdge)
				if not net.union(idx, leftChild[idx]):
					return False
			if rightChild[idx] != -1:
				rightEdge = (min(idx, rightChild[idx]), max(idx, rightChild[idx]))
				if rightEdge in edges:
					return False
				edges.add(rightEdge)
				if not net.union(idx, rightChild[idx]):
					return False
		return len(edges) == n - 1


class Solution:

	def validateBinaryTreeNodes(self, n, left, right):
		roots = {*range(n)}
		for x in left + right:
			if x == -1:
				continue
			if x not in roots:
				return False
			roots.discard(x)
		if len(roots) != 1:
			return False
		k = 0
		stk = [roots.pop()]
		while stk:
			node = stk.pop()
			k += 1
			(l, r) = (left[node], right[node])
			if l != -1:
				stk.append(l)
			if r != -1:
				stk.append(r)
		return k == n


class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		vis = set()
		heads = set()

		def dfs(i):
			if i == -1:
				return True
			vis.add(i)
			for child in [leftChild[i], rightChild[i]]:
				if child in vis:
					if child not in heads:
						return False
					else:
						heads.remove(child)
				elif not dfs(child):
					return False
			return True
		for i in range(n):
			if i not in vis:
				if not dfs(i):
					return False
				heads.add(i)
		return len(heads) == 1


class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		unvisited = set([i for i in range(n)])
		graph = defaultdict(set)
		for i in range(len(leftChild)):
			if leftChild[i] != -1:
				graph[i].add(leftChild[i])
		for i in range(len(rightChild)):
			if rightChild[i] != -1:
				graph[i].add(rightChild[i])
		zero_indegree_nodes = set(unvisited)
		for (k, v) in graph.items():
			for node in v:
				if node in zero_indegree_nodes:
					zero_indegree_nodes.remove(node)
		if len(zero_indegree_nodes) != 1:
			return False

		def visit(node):
			unvisited.remove(node)
			for nbr in graph[node]:
				if nbr not in unvisited:
					return True
				if visit(nbr):
					return True
			return False
		x = visit(list(zero_indegree_nodes)[0])
		if x == True:
			return False
		if len(unvisited) > 0:
			return False
		return True


from collections import defaultdict

class Solution:

	def DFS(self, edges, root, visited):
		for child in edges[root]:
			if child in visited:
				return False
			else:
				visited.add(child)
				if not self.DFS(edges, child, visited):
					return False
		return True

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		master_list = leftChild + rightChild
		children = set(master_list) - set([-1])
		parent = set(range(n)) - children
		if len(parent) != 1:
			return False
		parent = list(parent)[0]
		edges = defaultdict(list)
		for i in range(n):
			if leftChild[i] != -1:
				edges[i].append(leftChild[i])
			if rightChild[i] != -1:
				edges[i].append(rightChild[i])
		visited = set()
		visited.add(parent)
		if not self.DFS(edges, parent, visited):
			return False
		return len(visited) == n


class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		indegree = [0] * n
		outdegree = [0] * n
		visited = [False] * n
		possible_roots = []
		for i in range(n):
			if leftChild[i] != -1:
				outdegree[i] += 1
				indegree[leftChild[i]] += 1
			if rightChild[i] != -1:
				outdegree[i] += 1
				indegree[rightChild[i]] += 1
		for i in range(n):
			if indegree[i] == 0 and outdegree[i] <= 2:
				possible_roots.append(i)
				if len(possible_roots) > 1:
					return False
			if outdegree[i] > 2:
				return False
		if not possible_roots:
			return False
		queue = deque()
		queue.append(possible_roots[0])
		while queue:
			node = queue.popleft()
			if visited[node]:
				return False
			visited[node] = True
			lc = leftChild[node]
			rc = rightChild[node]
			if lc != -1:
				queue.append(lc)
			if rc != -1:
				queue.append(rc)
		return all(visited)


from typing import List
from collections import defaultdict

class DS:

	def __init__(self, n):
		self.sz = [1] * n
		self.rt = [i for i in range(n)]
		self.ccCt = n

	def query(self, x):
		root = x
		while root != self.rt[root]:
			self.rt[root] = self.rt[self.rt[root]]
			root = self.rt[root]
		return root

	def union(self, x, y):
		(rootX, rootY) = (self.query(x), self.query(y))
		if rootX != rootY:
			self.ccCt -= 1
			(szX, szY) = (self.sz[rootX], self.sz[rootY])
			if szX < szY:
				self.sz[rootY] += szX
				self.rt[rootX] = rootY
			else:
				self.sz[rootX] += szY
				self.rt[rootY] = rootX

	def cc(self):
		return self.ccCt

class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		ds = DS(n)
		edgeCt = 0
		for node in range(n):
			(l, r) = (leftChild[node], rightChild[node])
			for c in (l, r):
				if c != -1:
					edgeCt += 1
					ds.union(node, c)
		return n - 1 == edgeCt and ds.cc() == 1


class DSU:

	def __init__(self, n):
		self.p = [-1] * n
		self.r = [0] * n

	def find(self, x):
		if self.p[x] == -1:
			return x
		self.p[x] = self.find(self.p[x])
		return self.p[x]

	def union(self, x, y):
		r_x = self.find(x)
		r_y = self.find(y)
		if r_x == r_y:
			return False
		if self.r[r_x] > self.r[r_y]:
			self.p[r_y] = r_x
		else:
			self.p[r_x] = r_y
			if self.r[r_x] == self.r[r_y]:
				self.r[r_x] += 1
		return True

class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		dsu = DSU(n)
		for i in range(n):
			if leftChild[i] != -1 and (not dsu.union(i, leftChild[i])):
				return False
			if rightChild[i] != -1 and (not dsu.union(i, rightChild[i])):
				return False
		return len([1 for i in range(n) if dsu.p[i] == -1]) == 1


class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:

		def find(u):
			if p[u] != u:
				p[u] = find(p[u])
			return p[u]

		def union(u, v):
			(pU, pV) = (find(u), find(v))
			if pU == pV:
				return False
			(rmin, rmax) = (pU, pV) if rank[pU] < rank[pV] else (pV, pU)
			p[rmin] = rmax
			rank[rmax] += rank[rmin] == rank[rmax]
			return True
		group = n
		(p, rank) = (list(range(n)), [0] * n)
		for i in range(n):
			for j in [leftChild[i], rightChild[i]]:
				if j > -1:
					if not union(i, j):
						return False
					group -= 1
		return group == 1


class Solution:

	def validateBinaryTreeNodes(self, n: int, l: List[int], r: List[int]) -> bool:
		s = set()
		d = [0] * n
		for i in l:
			if i != -1:
				d[i] = 1
		for i in r:
			if i != -1:
				d[i] = 1
		q = []
		for i in range(n):
			if not d[i]:
				q.append(i)
				break
		if len(q) == 0:
			return False
		while len(q):
			t = q.pop()
			s.add(t)
			if l[t] in s or r[t] in s:
				return False
			if l[t] != -1:
				q.append(l[t])
			if r[t] != -1:
				q.append(r[t])
		if len(s) == n:
			return True
		else:
			return False


class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:

		def find(x):
			if x != par[x]:
				par[x] = find(par[x])
			return par[x]

		def union(x, y):
			(x, y) = list(map(find, [x, y]))
			if x != y:
				if rank[x] < rank[y]:
					(x, y) = (y, x)
				par[y] = x
				rank[x] += rank[x] == rank[y]
				return True
			else:
				return False
		indegree = [0] * n
		cnt = n
		par = list(range(n))
		rank = [0] * n
		for (parent, (l, r)) in enumerate(zip(leftChild, rightChild)):
			if l != -1:
				indegree[l] += 1
				if union(parent, l):
					cnt -= 1
			if r != -1:
				indegree[r] += 1
				if union(parent, r):
					cnt -= 1
		return sum(indegree) == n - 1 and cnt == 1


class UnionFind:

	def __init__(self, n):
		self.parent = list(range(n))
		self.count = n

	def find(self, x):
		if self.parent[x] != x:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, x, y):
		(px, py) = (self.find(x), self.find(y))
		if px != py:
			self.count -= 1
			self.parent[px] = py

class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		inDegree = [0] * n
		uf = UnionFind(n)
		for (parent, nodes) in enumerate(zip(leftChild, rightChild)):
			(l, r) = nodes
			if l != -1:
				inDegree[l] += 1
				uf.union(l, parent)
			if r != -1:
				inDegree[r] += 1
				uf.union(r, parent)
		return sum(inDegree) == n - 1 and uf.count == 1


class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:

		def bfs(n):
			if n not in self.remainingNodes:
				self.isValid = False
				return
			self.remainingNodes.remove(n)
			if len(nodes[n]) > 2:
				self.isValid = False
				return
			for child in nodes[n]:
				if child != -1 and child not in self.remainingNodes:
					self.isValid = False
					return
				if child != -1:
					bfs(child)

		def findRoot():
			if len(leftChild) == 1:
				if leftChild[0] == rightChild[0] == -1:
					return 0
			for node in parents:
				for parent in parents[node]:
					if parent not in parents:
						return parent
		nodes = collections.defaultdict(list)
		parents = collections.defaultdict(list)
		for i in range(len(leftChild)):
			if leftChild[i] != -1:
				nodes[i].append(leftChild[i])
				parents[leftChild[i]].append(i)
			if rightChild[i] != -1:
				nodes[i].append(rightChild[i])
				parents[rightChild[i]].append(i)
		self.isValid = True
		self.remainingNodes = set((i for i in range(n)))
		root = findRoot()
		bfs(root)
		return self.isValid and (not self.remainingNodes)


class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		rec = set()
		log = {}

		def check(ind, tar):
			if ind == -1:
				return False
			if ind in log:
				if log[ind] == tar:
					return True
				return check(log[ind], tar)
			return False
		for (ind, (i, j)) in enumerate(zip(leftChild, rightChild)):
			if i != -1:
				if i in rec:
					return False
				rec.add(i)
				log[i] = ind
				if check(ind, i):
					return False
			if j != -1:
				if j in rec:
					return False
				rec.add(j)
				log[j] = ind
				if check(ind, j):
					return False
		if len(rec) + 1 != n:
			return False
		return True


class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		parents = [-1] * n
		for p in range(n):
			if leftChild[p] != -1:
				if parents[leftChild[p]] != -1:
					return False
				parents[leftChild[p]] = p
			if rightChild[p] != -1:
				if parents[rightChild[p]] != -1:
					return False
				parents[rightChild[p]] = p
		found = False
		for p in parents:
			if p == -1:
				if found:
					return False
				found = True
		visit = [0] * n

		def dfs(ix):
			if ix == -1:
				return True
			if visit[ix] == 1:
				return False
			visit[ix] = 1
			if not dfs(parents[ix]):
				return False
			visit[ix] = 2
			return True
		for i in range(n):
			if visit[i] == 2:
				continue
			if not dfs(i):
				return False
		return True


class UnionFind:

	def __init__(self, n):
		self.parent = list(range(n))
		self.count = n

	def find(self, x):
		if self.parent[x] != x:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, x, y):
		(parent_x, parent_y) = (self.find(x), self.find(y))
		if parent_x != parent_y:
			self.parent[parent_x] = parent_y
			self.count -= 1

class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		parent = [0] * n
		uf = UnionFind(n)
		for (prev, childs) in enumerate(zip(leftChild, rightChild)):
			(l, r) = childs
			if l != -1:
				parent[l] += 1
				uf.union(l, prev)
			if r != -1:
				parent[r] += 1
				uf.union(r, prev)
		return sum(parent) == n - 1 and uf.count == 1


class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		visited = set()
		for i in range(n):
			if leftChild[i] != -1:
				visited.add(leftChild[i])
			if rightChild[i] != -1:
				visited.add(rightChild[i])
		queue = list(set(list(range(n))) - visited)
		if len(queue) != 1:
			return False
		visited = set()
		while queue:
			curr = queue.copy()
			queue = []
			for c in curr:
				if c in visited:
					return False
				visited.add(c)
				if leftChild[c] != -1:
					queue.append(leftChild[c])
				if rightChild[c] != -1:
					queue.append(rightChild[c])
		return len(visited) == n


class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		check_list = [0] * n
		for node in range(n):
			left_node = leftChild[node]
			right_node = rightChild[node]
			if left_node >= 0:
				check_list[left_node] += 1
			if right_node >= 0:
				check_list[right_node] += 1
		print(check_list)
		zero_num = check_list.count(0)
		if zero_num != 1:
			return False
		if max(check_list) > 1:
			return False
		root_node = check_list.index(0)
		check_list = [0] * n

		def check_binary_tree(node, check_list):
			check_list[node] += 1
			left_node = leftChild[node]
			right_node = rightChild[node]
			if left_node >= 0:
				check_binary_tree(left_node, check_list)
			if right_node >= 0:
				check_binary_tree(right_node, check_list)
		check_binary_tree(root_node, check_list)
		(min_n, max_n) = (min(check_list), max(check_list))
		print(check_list)
		if not (min_n == 1 and max_n == 1):
			return False
		return True


class Node:

	def __init__(self, val=0, left=None, right=None):
		self.val = val
		self.left = left
		self.right = right

class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		(all_nodes, root_nodes) = self.gen_graph(leftChild, rightChild)
		if len(root_nodes) != 1:
			return False
		visited = {all_nodes[root_nodes[0]]}

		def dfs(node):
			if node.left and node.left in visited:
				return False
			if node.right and node.right in visited:
				return False
			if node.left:
				visited.add(node.left)
				if not dfs(node.left):
					return False
			if node.right:
				visited.add(node.right)
				if not dfs(node.right):
					return False
			return True
		if not dfs(all_nodes[root_nodes[0]]):
			return False
		for i in range(len(leftChild)):
			if all_nodes[i] not in visited:
				return False
		return True

	def gen_graph(self, left_child, right_child):
		nodes = defaultdict(lambda : Node())
		indegrees = defaultdict(int)
		for i in range(len(left_child)):
			node = nodes[i]
			if left_child[i] != -1:
				node.left = nodes[left_child[i]]
				indegrees[left_child[i]] += 1
			if right_child[i] != -1:
				node.right = nodes[right_child[i]]
				indegrees[right_child[i]] += 1
		root_nodes = [i for i in range(len(left_child)) if indegrees[i] == 0]
		return (nodes, root_nodes)


class Dsu:

	def __init__(self, n):
		self.p = [x for x in range(n)]
		self.r = [0 for x in range(n)]

	def find(self, x):
		if self.p[x] != x:
			self.p[x] = self.find(self.p[x])
		return self.p[x]

	def union(self, x, y):
		(xx, yy) = (self.find(x), self.find(y))
		if xx == yy:
			return True
		if self.r[xx] > self.r[yy]:
			self.p[yy] = xx
		elif self.r[yy] > self.r[xx]:
			self.p[xx] = yy
		else:
			self.r[xx] += 1
			self.p[yy] = xx
		return False

class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		n = len(leftChild)
		x = 0
		y = 0
		z = 0
		f = [0 for i in range(n)]
		h = Dsu(n)
		for i in range(n):
			if leftChild[i] != -1:
				f[leftChild[i]] += 1
				h.union(i, leftChild[i])
			if rightChild[i] != -1:
				f[rightChild[i]] += 1
				h.union(i, rightChild[i])
		for (i, ii) in enumerate(f):
			if ii > 1:
				x += 1
			if h.find(i) == i:
				y += 1
			if ii == 0:
				z += 1
		if y != 1:
			return False
		elif z != 1:
			return False
		elif x > 0:
			return False
		else:
			return True


class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		allChildren = [n for n in leftChild + rightChild if n != -1]
		allChildrenSet = set(allChildren)
		if not len(allChildren) == len(allChildrenSet):
			return False
		root = [i for i in range(n) if i not in allChildrenSet]
		if len(root) != 1:
			return False
		root = root[0]
		stk = [root]
		while stk:
			n = stk.pop()
			allChildrenSet.discard(n)
			stk.extend([c for c in [leftChild[n], rightChild[n]] if c != -1])
		return not allChildrenSet


class UnionFind:

	def __init__(self, n):
		self.reps = [i for i in range(n)]
		self.size = n

	def find(self, x):
		while x != self.reps[x]:
			self.reps[x] = self.reps[self.reps[x]]
			x = self.reps[x]
		return x

	def union(self, x, y):
		x_root = self.find(x)
		y_root = self.find(y)
		if x_root == y_root:
			return
		self.size -= 1
		self.reps[x] = y_root

class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		p2c = collections.defaultdict(set)
		c2p = collections.defaultdict(set)
		uf = UnionFind(n)
		for (i, (l, r)) in enumerate(zip(leftChild, rightChild)):
			if l != -1:
				p2c[i].add(l)
				c2p[l].add(i)
				uf.union(i, l)
				if i in p2c[l]:
					return False
			if r != -1:
				p2c[i].add(r)
				c2p[r].add(i)
				uf.union(i, r)
				if i in p2c[r]:
					return False
		for i in range(n):
			if len(c2p[i]) > 1:
				return False
		return uf.size == 1


class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		graph = collections.defaultdict(list)
		indegree = {nodeNum: 0 for nodeNum in range(n)}
		for nodeNum in range(n):
			left = leftChild[nodeNum]
			right = rightChild[nodeNum]
			graph[nodeNum] = []
			if left != -1:
				graph[nodeNum].append(left)
				indegree[left] += 1
			if right != -1:
				graph[nodeNum].append(right)
				indegree[right] += 1
		zeroIndegrees = collections.deque([])
		singleIndegrees = 0
		for (nodeNum, indegrees) in list(indegree.items()):
			if indegrees == 0:
				zeroIndegrees.append(nodeNum)
			elif indegrees == 1:
				singleIndegrees += 1
			else:
				return False
		if len(zeroIndegrees) != 1:
			return False
		if len(zeroIndegrees) + singleIndegrees != n:
			return False
		print(zeroIndegrees)
		topological_sort = []
		while zeroIndegrees:
			nodeNum = zeroIndegrees.popleft()
			topological_sort.append(nodeNum)
			if nodeNum in graph:
				for child in graph[nodeNum]:
					indegree[child] -= 1
					if indegree[child] == 0:
						zeroIndegrees.append(child)
		if len(topological_sort) == n:
			return True
		return False


class Solution:

	def validateBinaryTreeNodes(self, N: int, leftChild: List[int], rightChild: List[int]) -> bool:
		(inNodes, outNodes) = (collections.defaultdict(set), collections.defaultdict(set))
		for (n, c) in enumerate(leftChild):
			if c != -1:
				outNodes[n].add(c)
				inNodes[c].add(n)
		for (n, c) in enumerate(rightChild):
			if c != -1:
				outNodes[n].add(c)
				inNodes[c].add(n)
		zeroInDegree = 0
		root = None
		for i in range(N):
			if len(inNodes[i]) > 1:
				return False
			if not inNodes[i]:
				root = i
				zeroInDegree += 1
		if zeroInDegree != 1:
			return False

		def hasCycle(n, visited):
			visited.add(n)
			for nb in outNodes[n]:
				if nb in visited:
					return True
				if hasCycle(nb, visited):
					return True
			return False
		visited = set()
		if hasCycle(root, visited):
			return False
		if len(visited) != N:
			return False
		return True


class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		indegrees = [0] * n
		root = -1
		for i in range(n):
			left = leftChild[i]
			if left != -1:
				indegrees[left] += 1
				if indegrees[left] > 1:
					return False
			right = rightChild[i]
			if right != -1:
				indegrees[right] += 1
				if indegrees[right] > 1:
					return False
		for i in range(n):
			if indegrees[i] == 0:
				if root == -1:
					root = i
				else:
					return False
		if root == -1:
			return False

		def count(node):
			if node == -1:
				return 0
			return 1 + count(leftChild[node]) + count(rightChild[node])
		return count(root) == n


class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		indegree = [0 for _ in range(n)]
		roots = set(range(n))
		children = set()
		for (left, right) in zip(leftChild, rightChild):
			if left != -1:
				indegree[left] += 1
				if left in roots:
					roots.remove(left)
					children.add(left)
				if indegree[left] > 1:
					return False
			if right != -1:
				indegree[right] += 1
				if right in roots:
					roots.remove(right)
					children.add(right)
				if indegree[right] > 1:
					return False
		if len(roots) != 1:
			return False
		while roots:
			new_root = next(iter(roots))
			roots.remove(new_root)
			if leftChild[new_root] != -1:
				children.remove(leftChild[new_root])
				roots.add(leftChild[new_root])
			if rightChild[new_root] != -1:
				children.remove(rightChild[new_root])
				roots.add(rightChild[new_root])
		return not children


class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		indict = defaultdict(list)
		outdict = defaultdict(list)
		for i in range(n):
			if leftChild[i] != -1:
				outdict[i].append(leftChild[i])
				indict[leftChild[i]].append(i)
			if rightChild[i] != -1:
				outdict[i].append(rightChild[i])
				indict[rightChild[i]].append(i)
		rootcount = []
		for nownode in range(n):
			innodelist = indict[nownode]
			if len(innodelist) == 0:
				rootcount.append(nownode)
			if len(innodelist) > 1:
				return False
			for innode in innodelist:
				if innode in outdict[nownode]:
					return False
		if len(rootcount) != 1:
			return False
		root = rootcount[0]
		ans = []
		visited = {}

		def traverse(node):
			if node == -1:
				return True
			if node in visited:
				return False
			visited[node] = 1
			resleft = traverse(leftChild[node])
			ans.append(node)
			resright = traverse(rightChild[node])
			if resleft == False or resright == False:
				return False
			return True
		res = traverse(root)
		if len(ans) == n and res == True:
			return True
		return False


class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		ingress = [0] * n
		g = defaultdict(list)
		for i in range(n):
			if leftChild[i] != -1:
				ingress[leftChild[i]] += 1
				g[i].append(leftChild[i])
			if rightChild[i] != -1:
				ingress[rightChild[i]] += 1
				g[i].append(rightChild[i])
		if ingress.count(0) > 1 or max(ingress) > 1:
			return False

		def dfs(node):
			visited.add(node)
			visiting.add(node)
			for neigh in g[node]:
				if neigh not in visited and dfs(neigh):
					return True
				elif neigh in visiting:
					return True
			visiting.remove(node)
			return False
		visited = set()
		visiting = set()
		for i in range(n):
			if i not in visited:
				if dfs(i):
					return False
		return True


class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		parent = {x: 0 for x in range(n)}
		child = [0] * n
		val = {0: 0, 1: 0}
		for i in range(n):
			if leftChild[i] != -1:
				parent[leftChild[i]] += 1
				child[i] += 1
				if parent[leftChild[i]] > 1:
					return False
			if rightChild[i] != -1:
				parent[rightChild[i]] += 1
				child[i] += 1
				if parent[rightChild[i]] > 1:
					return False
		self.ans = 1

		def dfs(node):
			if leftChild[node] != -1:
				self.ans += 1
				dfs(leftChild[node])
			if rightChild[node] != -1:
				self.ans += 1
				dfs(rightChild[node])
		for i in range(n):
			val[parent[i]] += 1
			if parent[i] == 0:
				dfs(i)
		if self.ans == n:
			return True
		return False


class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		children = set()
		children.add(0)
		for i in range(n):
			l = [leftChild[i], rightChild[i]]
			for c in l:
				if c != -1:
					if i in children:
						if c in children:
							return False
						else:
							children.add(c)
					elif c in children:
						children.add(i)
					else:
						return False
		return len(children) == n


class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		parent = list(range(n))
		degree = [0] * n
		count = n

		def find(x):
			if parent[x] != x:
				parent[x] = find(parent[x])
			return parent[x]

		def union(x, y):
			nonlocal count, parent
			(xp, yp) = (find(x), find(y))
			if xp != yp:
				count -= 1
				parent[yp] = xp
		for (par, nodes) in enumerate(zip(leftChild, rightChild)):
			(l, r) = nodes
			if l != -1:
				degree[l] += 1
				union(par, l)
			if r != -1:
				degree[r] += 1
				union(par, r)
		return True if sum(degree) == n - 1 and count == 1 else False


class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		g = defaultdict(list)
		root = set(range(n))
		for (i, (l, r)) in enumerate(zip(leftChild, rightChild)):
			g[i] += [l, r]
			root.discard(l)
			root.discard(r)
		if len(root) != 1:
			return False
		seen = set()

		def trav(cur):
			if cur in seen:
				return False
			if not g[cur]:
				return True
			seen.add(cur)
			if len(g[cur]) > 2:
				return False
			return all((trav(nxt) for nxt in g[cur]))
		if not trav(root.pop()):
			return False
		return len(seen) == n


class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:

		def findRoot():
			for (l, r) in zip(leftChild, rightChild):
				if l != -1:
					inDegree[l] += 1
				if r != -1:
					inDegree[r] += 1
			for (i, count) in enumerate(inDegree):
				if count == 0:
					return i
			return -1

		def dfs(i):
			l = leftChild[i]
			r = rightChild[i]
			if visited[i] or (l != -1 and visited[l]) or (r != -1 and visited[r]):
				return False
			visited[i] = True
			if l == -1 and r == -1:
				return True
			elif l == -1:
				return dfs(r)
			elif r == -1:
				return dfs(l)
			else:
				return dfs(l) and dfs(r)
		inDegree = [0 for _ in range(n)]
		visited = [False for _ in range(n)]
		root = findRoot()
		if root == -1:
			return False
		ok = dfs(root)
		if not ok:
			return False
		return all(visited)


class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		graph = collections.defaultdict(list)
		edges = 0
		indegree = [0] * n
		for i in range(n):
			if leftChild[i] >= 0:
				graph[i].append(leftChild[i])
				indegree[leftChild[i]] += 1
				edges += 1
			if rightChild[i] >= 0:
				graph[i].append(rightChild[i])
				indegree[rightChild[i]] += 1
				edges += 1
		if edges != n - 1:
			return False
		q = []
		for i in range(n):
			if indegree[i] == 0:
				q.append(i)
		if len(q) != 1:
			return False
		while q:
			l = len(q)
			for _ in range(l):
				cur = q.pop()
				n -= 1
				for nei in graph[cur]:
					indegree[nei] -= 1
					if indegree[nei] == 0:
						q.append(nei)
		return n == 0


class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:

		def find(u):
			if p[u] != u:
				p[u] = find(p[u])
			return p[u]

		def union(u, v):
			(pU, pV) = (find(u), find(v))
			if pU == pV:
				return False
			(rmin, rmax) = (pU, pV) if rank[pU] < rank[pV] else (pV, pU)
			p[rmin] = rmax
			rank[rmax] += rank[rmin] == rank[rmax]
			return True
		(incoming, outgoing) = (list(range(n)), defaultdict(list))
		for i in range(n):
			(l, r) = (leftChild[i], rightChild[i])
			if l == i or r == i:
				return False
			if l > -1:
				if i in outgoing[l]:
					return False
				outgoing[i].append(l)
				if incoming[l] != l:
					return False
				incoming[l] = i
			if r > -1:
				if i in outgoing[r]:
					return False
				outgoing[i].append(r)
				if incoming[r] != r:
					return False
				incoming[r] = i
		group = n
		(p, rank) = (list(range(n)), [0] * n)
		for i in range(n):
			for j in outgoing[i]:
				if not union(i, j):
					return False
				group -= 1
		return group == 1


class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		uf = {}

		def find(x):
			uf.setdefault(x, x)
			if uf[x] != x:
				uf[x] = find(uf[x])
			return uf[x]

		def union(x, y):
			uf[find(x)] = find(y)
		(indegree, outdegree) = (Counter(), Counter())
		root_cnt = 0
		for (i, node) in enumerate(leftChild):
			if node == -1:
				continue
			indegree[node] += 1
			outdegree[i] += 1
			union(i, node)
		for (i, node) in enumerate(rightChild):
			if node == -1:
				continue
			indegree[node] += 1
			outdegree[i] += 1
			union(i, node)
		for i in range(n):
			if indegree[i] == 0:
				root_cnt += 1
			elif indegree[i] != 1:
				return False
			if outdegree[i] > 2:
				return False
		return root_cnt == 1 and len(set(map(find, list(range(n))))) == 1


from collections import deque

class Solution:

	def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
		q = deque()
		visited = [0 for _ in range(len(leftChild))]
		root = 0
		store = set([i for i in range(len(leftChild))])
		for i in range(len(leftChild)):
			left = leftChild[i]
			right = rightChild[i]
			store.discard(left)
			store.discard(right)
		print(store)
		for i in store:
			root = i
			break
		q.append(root)
		while len(q) > 0:
			element = q.popleft()
			visited[element] = 1
			left = leftChild[element]
			right = rightChild[element]
			if left != -1:
				if left in q or visited[left] == 1:
					return False
				else:
					q.append(left)
			if right != -1:
				if right in q or visited[right] == 1:
					return False
				else:
					q.append(right)
		for i in visited:
			if i == 0:
				return False
		return True