Min-cut partitioning a graph using kernighan Lin algorithm
KL algorithm is an old heuristic algorithm for partitioning a graph into two parts, with equal number of vertices in each part, and as small as possible number of cuts between the two parts.
Since it is a heuristic algorithm, the minimality is not guaranteed.
The first line specifies the number of nodes |V|, and the number of edges |E|
The nodes then are numbered 1 to |V|. The following |E| lines specify edges
Note that there could be unconnected nodes, i.e., nodes not connected to any other nodes.
$ kl input