code

# vim: set syntax=python filetype=python:

import msgpack

def makeTwoGroup(vertexCount, constraints):
	verticesGroup = [None] * vertexCount
	
	for i in range(0, len(constraints), 2):
		v1, v2 = constraints[i], constraints[i + 1]
		
		if verticesGroup[v1] == verticesGroup[v2] != None:
			return [], []

		elif verticesGroup[v1] == 1:
			verticesGroup[v2] = 2
		elif verticesGroup[v1] == 2:
			verticesGroup[v2] = 1

		elif verticesGroup[v2] == 1:
			verticesGroup[v1] = 2
		elif verticesGroup[v2] == 2:
			verticesGroup[v1] = 1
		else:
			verticesGroup[v1] = 1
			verticesGroup[v2] = 2
	

	groupA, groupB = [], []
	for v, g in enumerate(verticesGroup):
		if g == 2:
			groupB.append(v)
		else:
			groupA.append(v)
	
	return groupA, groupB

	

with open("input.txt", "rb") as input_file, open("output.txt", "wb") as output_file:
	inPack = msgpack.Unpacker(input_file, use_list = True)

	problem_count = inPack.unpack()
	for i in xrange(problem_count):
		studentCount = inPack.unpack()
		friendship = inPack.unpack()

		paperA, paperB = makeTwoGroup(studentCount, friendship)
		msgpack.pack(paperA, output_file)
		msgpack.pack(paperB, output_file)