"""

Suppose we have some input data describing a graph of relationships between parents and children over multiple generations. The data is formatted as a list of (parent, child) pairs, where each individual is assigned a unique integer identifier.

For example, in this diagram, 3 is a child of 1 and 2, and 5 is a child of 4:


1   2   4
 \ /   / \
  3   5   8
   \ / \   \
    6   7   10

Write a function that, for two given individuals in our dataset, returns true if and only if they share at least one ancestor.


parentChildPairs, 3, 8 => false
parentChildPairs, 5, 8 => true
parentChildPairs, 6, 8 => true


"""

parent_child_pairs = [
    (1, 3), (2, 3), (3, 6), (5, 6),
    (5, 7), (4, 5), (4, 8), (8, 10)
]


def ancestor_comparison(p_c_p, node_a, node_b):
    a_ancestor = set()
    b_ancestor = set()
    for pair in p_c_p:
        child = pair[1]
        if child == node_a:
            a_ancestor.add(pair[0])
        if child == node_b:
            b_ancestor.add(pair[0])
    a_list = list(a_ancestor)
    for ancestor in a_list:
        # for pair in p_c_p:
        #     child = pair[1]
        #     if child == ancestor:
        #         a_ancestor.add(pair[0])
        check_parent(p_c_p, ancestor, a_ancestor)
    # print(a_ancestor)
    b_list = list(b_ancestor)
    for ancestor in b_list:
        # for pair in p_c_p:
        #     child = pair[1]
        #     if child == ancestor:
        #         b_ancestor.add(pair[0])
        check_parent(p_c_p, ancestor, b_ancestor)
    # print(b_ancestor)

    for ancestor in a_ancestor:
        if ancestor in b_ancestor:
            return True
    for ancestor in b_ancestor:
        if ancestor in a_ancestor:
            return True

    return False

def check_parent(p_c_p, node, ancestors):
    for pair in p_c_p:
        if pair[1] == node:
            ancestors.add(pair[0])
            check_parent(p_c_p, pair[0], ancestors)




print(ancestor_comparison(parent_child_pairs, 4, 8))



def graph_relationship(p_c_p):
    parent_dic = {}
    zero_parent = set()
    one_parent = set()
    for pair in p_c_p: # O(n) n number of pairs in p_c_p
        child = pair[1]
        if child in parent_dic:
            parent_dic[child] += 1
        else:
            parent_dic[child] = 1
    for pair in p_c_p: # O(n)
        child = pair[1]
        parent = pair[0]
        if child in parent_dic and parent_dic[child] == 1:
            one_parent.add(child)
        if parent not in parent_dic:
            zero_parent.add(parent)
    return [zero_parent, one_parent]

# print(graph_relationship(parent_child_pairs))