#!/usr/bin/python
# -*- coding: utf8 -*-
from sys import exit, stdout
from random import randint, seed, shuffle

seed('cockroach')
seeds = [randint(1, 10**9) for i in range(100)]
rnd = lambda n: randint(0, max(0, n - 1))

tests = set()

def out(*args):
    if len(args) == 1:        
        i = 1
        while i in tests:
            i += 1
        out(i, args[0])
    elif len(args) == 2:
        if type(args[0]) != int or type(args[1]) != str:
            print "Wrong parameters!"
            exit(2)            
        if args[0] in tests:
            print "Test number %d already exist!"%n
            exit(2)
        if args[0] > 99:
            print "Too many tests!"%n
            exit(3)
        stdout.write('[%02d]'%args[0])            
        stdout.flush()
        tests.add(args[0])
        seed(seeds[args[0]])
        open('%02d'%args[0], 'w').write(args[1])
    else:
        print "Wrong syntax!"
        exit(1)

def shuffle2(l):
    n = len(l)
    p = range(n + 1)
    shuffle(p)
    ans = [(p[i[0]], p[i[1]]) for i in l]
    shuffle(ans)
    return ans;

def from_parents(a):
    return [(k[0] + 1, k[1])  for k in enumerate(a)]

def gen_from(l, k):
    return '%d %d\n'%(len(l) + 1, k) + '\n'.join('%d %d'%(a[0] + 1, a[1] + 1) for a in l) + '\n'

def gen_rand(n, k):
    l = [rnd(i) for i in range(n - 1)]
    return gen_from(shuffle2(from_parents(l)), k)

def gen(l, k):
    return gen_from(from_parents(l), k)

def gen2(l, k):
    return gen_from(shuffle2(from_parents(l)), k)

def gen3(l, k):
    return gen_from(shuffle2(l), k)

def chain(n, k):
    return gen_from(shuffle2(from_parents(range(n - 1))), k)
    #return gen_from((from_parents(range(n - 1))), k)

# 01--05
out(gen([], 0))
out(gen([0], 0))
out(gen([0], 1))
out(gen2([0, 0, 1, 1, 2, 2], 2))
out(chain(10, 2))

# 06--10
out(gen_rand(18, 100))
out(gen_rand(18, 1))
out(gen_rand(18, 2))
out(gen_rand(18, 3))
out(gen2([0] * 17, 1))

# 11--15
out(chain(18, 1))
out(chain(18, 8))
out(chain(17, 8))
out(chain(18, 3))
out(gen_rand(18, 2))

# 16--20
out(gen2([0] * 16 + [1], 1))
out(gen2(range(7) * 2, 1 ))
out(gen_rand(18, 1))
out(gen_rand(18, 2))
out(gen2([0, 1, 2, 3, 4, 5, 6, 7] + [rnd(7) for i in range(7)], 2))

# 21--25
out(gen3( [(0, i) for i in range(1, 101)] + [(i + 1, 100 + i + 1) for i in range(100)], 1))
out(gen3( [(0, i) for i in range(1, 101)] + [(i + 1, 100 + i + 1) for i in range(100)], 2))
out(gen3( [((i - 1) // 2, i) for i in range(100)], 2))
out(chain(100, 48))
out(gen3( [(0, i) for i in range(1, 101)] + [(i + 1, 100 + i + 1) for i in range(100)] + [(100 + i + 1, 200 + i + 1) for i in range(100)], 2))

# 26--30
out(gen_rand(1000, 0))
out(gen_rand(2000, 1))
out(gen_rand(3000, 5))
out(gen_rand(10000, 10))
out(gen_rand(10000, 100))

# 31--35
out(chain(10000, 100))
out(chain(5000, 100))
out(gen3( [(0, i) for i in range(1, 5001)] + [(i + 1, 5000 + i + 1) for i in range(4999)], 1))
out(gen2( (range(1000) * 10)[:-1], 1))
out(gen3( [(0, i) for i in range(2, 4998)] + [(1, i) for i in range(4998, 9998)] + [(0, 1)], 1))

# 36--40
out(gen_rand(200000, 1))
out(gen_rand(200000, 2))
out(gen_rand(200000, 10))
out(gen_rand(200000, 20))
out(gen_rand(200000, 100))

# 41--45
out(chain(200000, 1))
out(chain(200000, 99999))
out(chain(200000, 100))
out(gen2([0] * 100000 + [1] * 99999, 1))
out(gen_rand(200000, 7))

# 46--50
out(gen3( [(0, i) for i in range(1, 100001)] + [(i + 1, 100000 + i + 1) for i in range(99999)], 1))
out(gen2( (range(20000) * 10)[:-1], 1))
out(gen3( [(0, i) for i in range(2, 99998)] + [(1, i) for i in range(99998, 199998)] + [(0, 1)], 1))
out(gen3( [(0, i) for i in range(1, 100001)] + [(i + 1, 100000 + i + 1) for i in range(99999)], 1))
out(gen3( [(0, i) for i in range(1, 100001)] + [(i + 1, 100000 + i + 1) for i in range(99999)], 2))
