def path_to_friend(network, user_A, user_B, path=None): #uses my second connection approach
    if not path: path=[]
    if (user_A or user_B) not in network.keys() :
        return None
    path=path + [user_A]
    if user_B in get_connections(network,user_A):
        return path + [user_B]
    common_connections=second_conn_in_common(network,user_A,user_B)
    if common_connections==0: # check if there is one connection between the two users
        next_connections=get_connections(network,user_A)
        for contact in next_connections:
            if contact not in path:
                final=path_to_friend(network,contact,user_B,path)
                if final:
                    return final
        return None
    elif common_connections>=1: # if one connection exists between two users, find the connection
        path=path + [middle_contact(network,user_A,user_B)]+[user_B]
        return path

def second_conn_in_common(network, user_A, user_B): #find if user_B is a second connection of User A
    if user_A not in network.keys():
        return False
    elif user_B not in network.keys():
        return False
    else:
        count=0
        for contact in network[user_A]['connected']:
            if user_B in network[contact]['connected']:
                count = count + 1
        return count


def middle_contact(network,user_A,user_B): # find the contact between user_A and user_B
    for contact in network[user_A]['connected']:
        if user_B in network[contact]['connected']:
            return contact


print path_to_friend(network, "Debra", "Mercedes")
print path_to_friend(network, "John", "Ollie")