import networkx as nx

# Erstelle einen Graphen, der das "Haus vom Nikolaus" darstellt
G = nx.Graph()
edges = [("A", "B"), ("A", "C"), ("A", "D"), ("B", "C"), ("B", "E"), ("C", "D"), ("C", "E"), ("D", "E")]
G.add_edges_from(edges)

# Finde alle Euler-Pfade im Graphen
eulerian_paths = list(nx.edge_dfs(G, source="A"))

# Filtere Pfade, die alle Kanten genau einmal verwenden
valid_paths = [path for path in eulerian_paths if len(path) == 9]

# Anzahl der gültigen Pfade ausgeben
print(
    f"Es gibt {len(valid_paths)} Möglichkeiten, das 'Haus vom Nikolaus' in einem Zug zu zeichnen, ohne den Stift abzusetzen."
)

# Alle gültigen Pfade ausgeben
for path in eulerian_paths:
    print(path)