import itertools

def sommet2str(sommet):
    gauche = "".join(str(p) for p in sorted(sommet[0]))
    droite = "".join(str(p) for p in sorted(sommet[1]))
    if sommet[2] == 0:
        gauche += "F"
    else:
        droite += "F"
    return f"{gauche}|{droite}"

if __name__ == "__main__":
    # [Gauche, Droite, Fermière]
    initial = [{"C", "L", "S"}, set(), 0]
    todo = [initial]
    done = []

    print("strict graph {")
    while todo:
        sommet = todo.pop()
        gauche, droite, fermière = sommet
        for perso in itertools.chain(sommet[fermière], [None]):
            nouveau = [gauche.copy(), droite.copy(), 1-fermière]
            if perso is not None:
                nouveau[fermière] -= {perso}
                nouveau[1-fermière] |= {perso}
            if nouveau not in todo and nouveau not in done:
                todo.append(nouveau)
                done.append(sommet)
            print("""   "{}" -- "{}" """.format(
                sommet2str(sommet),
                sommet2str(nouveau),
            ))
    print("""   "{}" [shape=doublecircle]""".format(sommet2str(initial)))

    final = [set(), {"C", "L", "S"}, 1]
    print("""   "{}" [shape=doublecircle]""".format(sommet2str(final)))

    for sommet in done:
        gauche, droite, fermière = sommet
        if ("C" in sommet[1-fermière] and "S" in sommet[1-fermière]) or ("C" in sommet[1-fermière] and "L" in sommet[1-fermière]):
            print("""  "{}" [color=red]""".format(sommet2str(sommet)))

    print("}")