i have a competition where we have to make a program that basicly find a path that browse all graphes nodes with specific rules (to browse to a node you have to have the same first name or last name and it change every move)

here’s my code, it works but it’s too slow, it needs to be faster :

def valid_http_path(gods, path):
    idx = 0
    gd = path[idx]
    for god in gods:
        if god == path[1]:
            begin_split = gd.split(" ")
            god_split = god.split(" ")
            if begin_split[0] == god_split[0]:
                v = 0
            elif begin_split[1] == god_split[1]:
                v = 1
            else:
                return False
    for way in path[1:]:
        if v == 0:   
            if gd.split(" ")[0] != way.split(" ")[0]:
                return False
        if v == 1:
            if gd.split(" ")[1] != way.split(" ")[1]:
                return False
        idx += 1
        gd = path[idx]
        v = (v+1)%2
    return set(path) == set(gods)

def way(gods, god, v):
    ways = []
    for gd in gods:
        if god != gd and god.split(" ")[v] == gd.split(" ")[v]:
            ways.append(gd)
    return ways

def build_graph(gods):
    graph = {}
    for god in gods:
        graph[god] = []
    for v in [0, 1]:
        for god in gods:
            graph[god].append(way(gods, god, v))
    return graph

def find_paths(graph, start, visited=None, path=None):
    if visited is None:
        visited = set()
    if path is None:
        path = []
    visited.add(start)
    path.append(start)
    paths = []
    for neighbor_list in graph[start]:
        for neighbor in neighbor_list:
            if neighbor not in visited:
                new_paths = find_paths(graph, neighbor, visited.copy(), path.copy())
                paths.extend(new_paths)
    if len(paths) == 0:
        paths.append(path)
    return paths

def find_all_paths(graph):
    all_paths = {}
    for vertex in graph:
        paths = find_paths(graph, vertex)
        all_paths[vertex] = paths
    return all_paths



N = int(input(""))
gods = [input("") for _ in range(N)]

pth = False
paths = find_all_paths(build_graph(gods))
for vertex in find_all_paths(build_graph(gods)):
    for path in paths[vertex]:
        if len(path) == len(gods) and valid_http_path(gods, path):
            pth = path 
if pth == False:
    print("IMPOSSIBLE")
else:
    for i in pth:
        print(i)

I tried a lot of things even using iterative algorithms but it did not work.