import random
import string

def make_groups(ppl, forbidden, gsize):
    assert len(ppl) % gsize == 0

    edges = set()
    for (a, b) in forbidden:
        edges.add((a, b))
        edges.add((b, a))

    ppl = list(ppl)
    random.shuffle(ppl)
    groups = [ ppl[gsize*i:gsize*(i+1)] for i in range(len(ppl) // gsize) ]

    while True:
        random.shuffle(groups)

        found_bad = False

        for g in groups:
            bad = []
            for i in range(gsize):
                for j in range(i + 1, gsize):
                    if (g[i], g[j]) in edges:
                        bad.append((i, j))

            if len(bad) > 0:
                found_bad = True
                fix = random.choice(random.choice(bad))
                other_group = random.randint(0, len(groups) - 1)
                other_idx = random.randint(0, gsize - 1)
                g[fix], groups[other_group][other_idx] = groups[other_group][other_idx], g[fix]

        if not found_bad:
            break

    return groups


def rand_str(n):
    return ''.join( random.choice(string.ascii_lowercase) for i in range(n) )

n = 200
ppl = set([ rand_str(5) for i in range(n) ])
forbidden = set()

for p in ppl:
    cnt = random.randint(0, 10)
    for c in range(cnt):
        forbidden.add((p, random.choice(list(ppl))))

print(ppl)
for a, b in forbidden:
    print(a, b)

for g in make_groups(ppl, forbidden, 4):

    for i in range(len(g)):
        for j in range(i + 1, len(g)):
            assert (g[i], g[j]) not in forbidden
            assert (g[j], g[i]) not in forbidden

    print(g)