import itertools
def read_graph(f):
"""
Read a nondirected graph from the file given as a parameter.
The form of the first line of the file is M N K. The vertex set of the
graph is V = {0, 1, ..., N - 1}. The next M lines contains U_i V_i pairs
expressing that U_i V_i is a nondirected edge. K is the number of
vertices in an independent set we are looking for.
The function returns a triple. The first object is a dictionary of the
edge list, the second is the number of vertices, the third is the size
of the independent set. The dictionary maps every vertex into the
list of neighboring vertices. If the list of the vertex U contains
the vertex V in its list, then U is in the list of the vertex V, as
the graph is nondirected.
:param f: the file containing the graph
:returns: triple of the dictionary of the edge list, N and K
"""
head = f.readline().split()
n, m, k = [int(s) for s in head]
graph = dict((i, []) for i in range(n))
for j in range(m):
edge = f.readline().split()
u, v = [int(s) for s in edge]
graph[u].append(v)
graph[v].append(u)
return graph, n, k
def combinations(a, b):
"""
Write the b-element combinations of the set {0, 1, 2, ..., a - 1}
to the standrad output.
"""
for comb in itertools.combinations(range(0, a), b):
print(" ".join(str(i) for i in comb))
if __name__ == '__main__':
import sys
with open(sys.argv[1], 'r') as f:
graph, n, k = read_graph(f)
# TODO Search for an independent set of k vertices
# (of course, change the next line in the final
# version and do not print out all combinations)
combinations(10, 3)