#!/opt/local/bin/python

import random, collections, string, copy

probname = "corporateretreat"

tcount = {}
total_secret = 0

# bounds like MAXN here
MAXN = 1000
MAXM = 5000
MAXK = 7

def gen(e, n, k, intype = probname):
    global total_secret

    assert n in range(1, MAXN+1)
    assert k in range(1, min(n,MAXK)+1)
    assert type(e) == list and len(e) in range(MAXM+1)
    edges = set()
    nbr = [False]*(n+1)
    for t in e:
        assert type(t) == tuple and len(t) == 2
        u, v = t
        assert u in range(1, n+1) and v in range(1, n+1) and u < v and t not in edges
        if u <= k: nbr[v] = True
        edges.add(t)
    assert all(nbr[k+1:])

    path = "../data"

    if intype not in tcount: tcount[intype] = 0
    tcount[intype] += 1

    if intype == "sample":
        filename = "{0}/sample/{1}.in".format(path, tcount[intype])
    else:
        filename = "{0}/secret/{3:02}-{1}-{2}.in".format(path, intype, tcount[intype], total_secret)
        total_secret += 1

    print("Generating:", filename)

    out = open(filename, "w")

    # print the test case here, remember to print to file=out
    print(n, k, len(e), file=out)
    for t in e: print(*t, file=out)

    out.close()

# E, N, K

def gensample():
    gen([(1,2),(1,3),(2,3),(2,4),(2,5),(3,4),(4,5)], 5, 2, "sample")
    gen([(1,2),(1,3),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)], 5, 2, "sample")
    gen([(1,3),(2,3)], 3, 2, "sample")
    

def gencorner():
    gen([], 1, 1, "corner")
    gen([(2,3)], 3, 2, "corner")
    gen([(1,2)], 2, 1, "corner")
    gen([(1,2)], 2, 2, "corner")
    gen([(1,2),(1,3),(2,3)], 3, 1, "corner")
    gen([(1,2),(1,3),(2,3)], 3, 2, "corner")
    gen([(1,2),(1,3),(2,3)], 3, 3, "corner")
    gen([(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)], 4, 1, "corner")
    gen([(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)], 4, 2, "corner")
    gen([(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)], 4, 3, "corner")
    gen([(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)], 4, 4, "corner")
    gen([(1,3),(1,4),(2,3),(2,4),(3,4)], 4, 2, "corner")
    gen([(1,3),(1,4),(2,3),(2,4),(3,4)], 4, 3, "corner")
    gen([(1,3),(1,4),(2,3),(2,4),(3,4)], 4, 4, "corner")
    gen([(1,2),(1,3),(1,4),(2,3),(2,4)], 4, 1, "corner")
    gen([(1,2),(1,3),(1,4),(2,3),(2,4)], 4, 2, "corner")
    gen([(1,2),(1,3),(1,4),(2,3),(2,4)], 4, 3, "corner")
    gen([(1,2),(1,3),(1,4),(2,3),(2,4)], 4, 4, "corner")


def gen_rand(N,M,K):
    e = [(i,j) for i in range(1, N+1) for j in range(i+1,N+1)]
    random.shuffle(e)

    used = set()
    for v in range(K+1,N+1): used.add((random.randint(1,K), v))

    for u,v in e:
        used.add((u,v))
        if len(used) == M: break
    
    gen(list(used), N, K, "random")

def gen_rand_yes(N,M,K):
    assert N >= 3 and K >= 3

    clr = [-1]*(N+1)
    while len(set(clr)) != 3: clr = [random.randint(1,3) for _ in range(N+1)]

    e = [(i,j) for i in range(1, N+1) for j in range(i+1,N+1)]
    random.shuffle(e)

    used = set()
    for v in range(K+1,N+1):
        x = v 
        while clr[x] == clr[v]: x = random.randint(1,K)
        used.add((x, v))

    for u, v in e:
        if clr[u] != clr[v]: used.add((u,v))
        if len(used) == M: break
    
    used = list(used)
    random.shuffle(used)

    gen(used, N, K, "random_yes")

def gen_rand_maybe_no(N,M,K):
    assert N >= 3

    clr = [-1]*(N+1)
    while len(set(clr)) != 3: clr = [random.randint(1,3) for _ in range(N+1)]

    e = [(i,j) for i in range(1, N+1) for j in range(i+1,N+1)]
    random.shuffle(e)

    used = set()
    for v in range(K+1,N+1):
        x = v 
        while clr[x] == clr[v]: x = random.randint(1,K)
        used.add((x, v))

    for u, v in e:
        if clr[u] != clr[v]: used.add((u,v))
        if len(used) > M*0.9: break
    
    for u, v in e:
        if clr[u] == clr[v]: used.add((u,v))
        if len(used) == M: break

    used = list(used)
    random.shuffle(used)

    gen(used, N, K, "random_maybe_no")

num_e = 0

def gen_greedy_break1():
    global num_e
    # two edges and a K3
    e = [(1,2),(1,3),(2,3),(4,5),(6,7)]
    trip = (MAXN-6)//3

    num_e = 7

    def get_emp(k):
        global num_e
        l = []
        while len(l) < k:
            num_e += 1
            l.append(num_e)
        return l
    
    def add(u,v): e.append((min(u,v),max(u,v)))


    # K3 of employees attached to matching edges
    a, b, c = get_emp(3)
    add(a,b)
    add(a,c)
    add(b,c)
    add(1,a)
    add(2,a)
    add(4,b)
    add(5,b)
    add(6,c)
    add(7,c)

    # attach p4s to an exec
    for x in [1,2,3]:
        for _ in range(80):
            emp = get_emp(4)
            a, b, c, d = emp
            add(x,a)
            add(x,b)
            add(x,c)
            add(x,d)
            add(a,b)
            add(b,c)
            add(c,d)

    random.shuffle(e)
    
    emps = list(range(8, num_e+1))
    random.shuffle(emps)
    emps = [0,1,2,3,4,5,6,7]+emps

    e_fnl = []
    for u,v in e:
        t = (emps[u], emps[v])
        e_fnl.append((min(t), max(t)))
    # print(num_e)

    gen(e_fnl,num_e,7,"greedy")

def gen_rand_break1():
    e = []

    GPS = (MAXN-1)//4
    for i in range(GPS):
        a, b, c, d = list(range(4*i+2, 4*i+6))
        e.extend([(1,a),(1,b),(1,c),(1,d),(a,b),(b,c),(c,d)])

    gen(e,4*GPS+1,1,"greedy")    

if __name__ == "__main__":
    random.seed(0)

    gensample()

    gencorner()

    gen_rand(10,30,4)
    gen_rand(100,300,4)

    gen_rand_yes(10, 30, 3)
    gen_rand_yes(10, 30, 4)
    gen_rand_yes(100,300,3)
    gen_rand_yes(100,300,4)


    for fn in [gen_rand, gen_rand_yes, gen_rand_maybe_no]:
        for K in [1,2,3,MAXK//2,MAXK]:
            if fn == gen_rand or K >= 3:
                fn(MAXN,MAXM,K)
    
    gen_greedy_break1()

    gen_rand_break1()