"""
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, 6 and 8 have a common ancestor of 4.

         14  13
         |   |
1   2    4   12
 \ /   / | \ /
  3   5  8  9
   \ / \     \
    6   7     11

parent_child_pairs_1 = [
    (1, 3), (2, 3), (3, 6), (5, 6), (5, 7),
    (4, 5),  (4, 8),
    (4, 9), (9, 11), (14, 4), (13, 12), (12, 9)
]

Write a function that takes the graph, as well as two of the individuals in our dataset, as its inputs and returns true if and only if they share at least one ancestor.

Sample input and output:

has_common_ancestor(parent_child_pairs_1, 3, 8) => false
has_common_ancestor(parent_child_pairs_1, 5, 8) => true
has_common_ancestor(parent_child_pairs_1, 6, 8) => true
has_common_ancestor(parent_child_pairs_1, 6, 9) => true
has_common_ancestor(parent_child_pairs_1, 1, 3) => false
has_common_ancestor(parent_child_pairs_1, 3, 1) => false
has_common_ancestor(parent_child_pairs_1, 7, 11) => true
has_common_ancestor(parent_child_pairs_1, 6, 5) => true
has_common_ancestor(parent_child_pairs_1, 5, 6) => true

Additional example: In this diagram, 4 and 12 have a common ancestor of 11.

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

parent_child_pairs_2 = [
    (11, 10), (11, 12), (2, 3), (10, 2), (10, 5),
    (1, 3), (3, 4), (5, 6), (5, 7), (7, 8),
]

has_common_ancestor(parent_child_pairs_2, 4, 12) => true
has_common_ancestor(parent_child_pairs_2, 1, 6) => false
has_common_ancestor(parent_child_pairs_2, 1, 12) => false

n: number of pairs in the input

"""

parent_child_pairs_1 = [
    (1, 3), (2, 3), (3, 6), (5, 6), (5, 7), (4, 5),
    (4, 8), (4, 9), (9, 11), (14, 4), (13, 12), (12, 9)
]

parent_child_pairs_2 = [
    (11, 10), (11, 12), (2, 3), (10, 2), (10, 5),
    (1, 3), (3, 4), (5, 6), (5, 7), (7, 8)
]

# TODO --- Write your abs

def has_common_ancestor(pairs, one,two):
    ancestors_one = []
    ancestors_two = []
    helper([one],ancestors_one,pairs)
    helper([two],ancestors_two,pairs)

    for item in ancestors_one:
        for item2 in ancestors_two:
            if item == item2:
                return True
    return False

    print(ancestors_one)
    print(ancestors_two)

def helper(my_input,ancestors,parent_child_pairs_1):
    queue = []
    #base case input in my_input is not a child
    flag = 0
    for node in my_input:
        for pair in parent_child_pairs_1:
            if node == pair[1]:
                flag = 1 # it's has a parent
    if (flag == 0):
        return
    #_______
    for node in my_input:
        for pair in parent_child_pairs_1:
            #every child parent pair where 6 is a child
            if node == pair[1]:
                queue.append(pair[0])
                ancestors.append(pair[0])
    helper(queue,ancestors,parent_child_pairs_1)

def find(pairs):
    my_dict = {}
    my_set = set()
    ret1 = []
    ret2 = []
    for pair in pairs:
        my_set.add(pair[0])
        my_set.add(pair[1])
        if pair[1] not in my_dict:
            my_dict[pair[1]] = 1
        else:
            my_dict[pair[1]] += 1

    for item in my_set:
        if item not in my_dict.keys():
            ret1.append(item)
    for item in my_dict:
        if my_dict[item] == 1:
            ret2.append(item)
    ret = []
    ret.append(ret1)
    ret.append(ret2)
    return ret

#     print(ret1)

# TODO --- Call your function with the test cases from above
print(has_common_ancestor(parent_child_pairs_1, 3, 8))
print(has_common_ancestor(parent_child_pairs_1, 5, 8))
print(has_common_ancestor(parent_child_pairs_1, 6, 8))
print(has_common_ancestor(parent_child_pairs_1, 6, 9))
print(has_common_ancestor(parent_child_pairs_1, 1, 3))
print(has_common_ancestor(parent_child_pairs_1, 3, 1))
print(has_common_ancestor(parent_child_pairs_1, 7, 11))
print(has_common_ancestor(parent_child_pairs_1, 6, 5))
print(has_common_ancestor(parent_child_pairs_1, 5, 6))

print(has_common_ancestor(parent_child_pairs_2, 4, 12))
print(has_common_ancestor(parent_child_pairs_2, 1, 6))
print(has_common_ancestor(parent_child_pairs_2, 1, 12))