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: interview

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
        
        #print(visited)
        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]
        
        # Returns false if the two elements are already in the same group
        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
        # [1, 3, 3, 3]
        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
        
#         print(children)
#         root = False
#         for i in range(n):
#             if i not in children:
#                 if root: 
#                     print('Here Yoyo')
#                     return False
#                 root = True
        
        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
            # print(cur)
            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: 
            # print('Count Small-',count)
            return False
        return True

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


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:
        # Conditions:
        # 1. There are one and only one node that has zero in degree.
        # 2. All other nodes have one and only one in degree.
        # 3. There are no cycle.
        
        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)
        # multiple roots or no root
        if counts[0] > 1 or counts[0] == 0:
            return False
        # multiple indegrees
        if any(count > 1 for count in list(counts.keys())):
            return False
        
        root = indeg.index(0)
        seen = [0]*n
        # no cycles and dfs hits all nodes (one CC)
        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
        
        #return method1()
    
        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, 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)
        # multiple roots or no root
        if counts[0] > 1 or counts[0] == 0:
            return False
        # multiple indegrees
        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, 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)}
        # print(parents)
        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
                
        # There must be exactly (n - 1) edges
        if num_edges != nodes - 1:
            return False
        
        # For each node, except for the root, there must be only 1 parent
        
        # FIND ALL ROOT NODES (IE. THOSE WITHOUT PARENT) - O(N)
        roots = [i for i in range(len(parents)) if parents[i] is None]

        # CHECK IF THERE'S EXACTLY 1 ROOT NODE  - O(1)
        if len(roots) != 1:
            return False
        
        # ENSURE ROOT HAS > 1 CHILD, IF N > 1 - O(N)
        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:

        # find root and do dfs
        # look for cycle or things not visited from the root
        visited = [False] * n
        cycle = False
        
        def dfs(root):
            nonlocal cycle
            #print(root, visited, 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
            # add -1 so u wont skip it
            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)
        #print(cycle)
        if cycle:
            #print('cycle')
            return False
        
        #print(visited)
        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
                else:
                    if 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)]
        # Count in-degree
        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
        # Find potential root
        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
        
        # Exactly n nodes in single tree
        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 dsu:
    def __init__(self,n):
        self.parent=list(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, x, y):
        
        px, py = self.find(x), self.find(y)
        
        if px==py:
            return False
        if px != py:
            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 Solution:   # 2020-10-09-7
    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
        # rules: (1) descendants cannot point to ancestors (i.e. no cycles)
        # (2) a node cannot be pointed to more than once (partly overlaps with rule 1)
        # (3) the tree should be connected, i.e. not a forest
        
        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)
                else:
                    if 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

#3:50
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)
                # check for more than one root node
                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)

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

        # find root and do dfs
        # look for cycle or things not visited from the root
        visited = [False] * n
        cycle = False
        
        def dfs(root):
            nonlocal cycle
            #print(root, visited, 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
            # add -1 so u wont skip it
            in_degree[-1] = 0    
            for i in range(n):
                in_degree[leftChild[i]] += 1
                in_degree[rightChild[i]] += 1
                
            for k,v in list(in_degree.items()):
                if v == 0:
                    return k
                
        root = find_root()
        #print(root)
        if root == None:
            return False
        dfs(root)
        #print(cycle)
        if cycle:
            #print('cycle')
            return False
        
        #print(visited)
        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)):
            # print(ind, i, j)
            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)
        ## check if it's separated tree or there's mutual arrow
        zero_num = check_list.count(0)
        if zero_num != 1:
            return False
        if max(check_list) > 1:
            return False
        
        ## check if it constructs binary tree
        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)
        # print(root_nodes)
        
        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
        # print(visited)
        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:
        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
        
        graph = defaultdict(list)
        for i in range(n):
            l, r = leftChild[i], rightChild[i]
            graph[i] += [l] if l > -1 else []
            graph[i] += [r] if r > -1 else []

        group = n
        p, rank = list(range(n)), [0] * n
        for i in range(n):
            for j in graph[i]:
                if not union(i, j): return False
                group -= 1
        return group == 1

class UnionFind:
    def __init__(self,n):
        self.parents = list(range(n ))
        self.count = n
        
    def find(self,x):
        if self.parents[x] != x:
            self.parents[x] = self.find(self.parents[x])
        return self.parents[x]
    
    def union(self,x,y):
        px = self.find(x)
        py = self.find(y)
        if px != py:
            self.count -= 1
            self.parents[px] = py
            
class Solution:
    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
        uf = UnionFind(n)
        indegree = [0] * n
        
        for parent,node in enumerate(zip(leftChild,rightChild)):
            l,r = node
            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:
        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.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 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 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:
        #  directed graph
        # each node except root has exactly 1 indegree
        # each node can have only 0~2 children
        
        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
                
        
        # print(indegree)
        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
    
# 4
# [1,0,3,-1]
# [-1,-1,-1,-1]

# 0               2
#     1         3
        


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)
    
        
        # 1. all in degrees must be <= 1 and only one should have in degree 0
        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
        
        # 2. cycle detection        
        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:
        # all nodes shoud not have more than 1 in degrees
        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
        
        # find the root with indegree == 0
        # if no root or multiple roots exist, return False
        for i in range(n):
            if indegrees[i] == 0:
                if root == -1:
                    root = i
                else:
                    return False
                
        if root == -1:
            return False
        
        # start from root, check node count == n
        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)
                
        #print(indict, outdict)
        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
        
        #print(rootcount)
        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)
        
        #print(ans)
        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)
        
        # construct a graph and ingress 
        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])
            
        # check only one root or two ingress
        if ingress.count(0) > 1 or max(ingress) > 1:
            return False
        
        # check any cycle
        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 # cycle detected
                
        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:
        # find root and do dfs
        # look for cycle or things not visited from the root
        visited = [False] * n
        cycle = False
        
        def dfs(root):
            nonlocal cycle
            #print(root, visited, 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
            # add -1 so u wont skip it
            in_degree[-1] = 0    
            for i in range(n):
                in_degree[leftChild[i]] += 1
                in_degree[rightChild[i]] += 1
                
            for k,v in list(in_degree.items()):
                if v == 0:
                    return k
                
        root = find_root()
        #print(root)
        if root == None:
            return False
        dfs(root)
        print(cycle)
        if cycle:
            #print('cycle')
            return False
        
        #print(visited)
        return all(visited)
        
        
                
            
            
        



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)
                    else:
                        if 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, 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
        root=roots.pop()
        stk=[root]
        k=0
        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:
        # find root and do dfs
        # look for cycle or things not visited from the root
        visited = [False] * n
        cycle = False
        
        def dfs(root):
            nonlocal cycle
            #print(root, visited, cycle)
            if root == -1:
                return
            
            if not visited[root]:
                visited[root] = True
                dfs(leftChild[root])
                dfs(rightChild[root])
            else:
                print('cycle')
                cycle = True
                
            
                   
        def find_root():
            in_degree = {}
            
            for i in range(n):
                in_degree[i] = 0
            # add -1 so u wont skip it
            in_degree[-1] = 0    
            for i in range(n):
                in_degree[leftChild[i]] += 1
                in_degree[rightChild[i]] += 1
                
            for k,v in list(in_degree.items()):
                if v == 0:
                    return k
                
        root = find_root()
        print(root)
        if root == None:
            return False
        dfs(root)
        print(cycle)
        if cycle:
            print('cycle')
            return False
        
        print(visited)
        return all(visited)
        
        
                
            
            
        





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)
        ## check if it's separated tree or there's mutual arrow
        zero_num = check_list.count(0)
        if zero_num != 1:
            return False
        if max(check_list) > 1:
            return False
        
        ## check if it constructs binary tree
        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 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]
            # No cycle allowed
            if l == i or r == i: return False
            if l > -1:
                # Every pair of nodes has only one edge: one-way not two-way edge
                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
        # Only one node has no incoming edge, others have only one incoming node
        # if sum([1 for i in range(n) if incoming[i] == i]) > 1: return False
        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 UnionFind:
    def __init__(self,n):
        self.parents = list(range(n))
        self.count = n
        
    def find(self,x):
        if self.parents[x] != x:
            self.parents[x] = self.find(self.parents[x])
        return self.parents[x]
    
    def union(self,x,y):
        px = self.find(x)
        py = self.find(y)
        
        if px != py:
            self.count -= 1
            self.parents[px] = py
            
            
class Solution:
    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
        uf = UnionFind(n)
        indegree = [0] * n
        
        for parent,node in enumerate(zip(leftChild,rightChild)):
            l,r = node
            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:
        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
    


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:
        parents = [idx for idx in range(n)]
        
        def find(idx):
            original_idx = idx
            height = 0
            while parents[idx] != idx:
                height += 1
                idx = parents[idx]
            parents[original_idx] = idx
            return idx, height
        
        # Returns false if the two elements are already in the same group
        def union(idx1, idx2):
            parent1, _ = find(idx1)
            parent2, _ = find(idx2)
            if parent1 == parent2:
                return False
            parents[parent1] = parent2
            return True
        # [1, 3, 3, 3]
        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 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)
        print(inDegree, uf.count)
        return sum(inDegree) == n - 1 and uf.count == 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