def eulerkreis(graph):
    # Erstelle ein Dictionary für die Nachbarn
    nachbarn = {knoten[0]: set(knoten[1]) for knoten in graph}
    
    # Überprüfe die Geradheit der Knotengrade
    for knoten in nachbarn:
        if len(nachbarn[knoten]) % 2 != 0:
            return False

    # Überprüfe die Zusammenhängigkeit des Graphen anhand Tiefensuche
    def dfs(knoten, besucht):
        besucht.add(knoten)
        for nachbar in nachbarn[knoten]:
            if nachbar not in besucht:
                dfs(nachbar, besucht)

    # Starte die DFS von einem beliebigen Knoten
    start_knoten = next(iter(nachbarn))
    besucht = set()
    dfs(start_knoten, besucht)

    # Überprüfe, ob alle Knoten besucht wurden
    return len(besucht) == len(nachbarn)

# Testdaten

graph1 = [
    ['1', ['2', '3']],
    ['2', ['1', '5', '4', '3']],
    ['3', ['2', '4', '5', '1']],
    ['4', ['2', '3']],
    ['5', ['2', '3']]
]

graph2 = [
    ['1', ['2', '3', '7', '8']],
    ['2', ['1', '3']],
    ['3', ['2', '1', '8', '4']],
    ['4', ['3', '7', '9', '5']],
    ['5', ['9', '4']],
    ['6', ['7', '9']],
    ['7', ['1', '4', '9', '6']],
    ['8', ['1', '3']],
    ['9', ['4', '7', '6', '5']],
]

from random import randint

def graph(n):
    graph = []
    for i in range(n):
        nachbarn = [randint(0, n-1) for _ in range(n)]
        graph.append([i, nachbarn])
    return graph



# Test
from time import *

knotenzahl = 100
testgrenze = 10000
while knotenzahl < testgrenze:
    aktuellerGraph = graph(knotenzahl)
    t1 = process_time()
    kreisExistiert = eulerkreis(aktuellerGraph)
    t2 = process_time()
    t = t2 - t1
    print(knotenzahl, t)
    knotenzahl *= 2