The Great Researcher Dr. Bari loves to do research. Once he was doing research on VLSI Circuit Design and came to know about graph partitioning.
In graph partitioning problem, you are given an undirected graph G with V vertices and E edges. The weights on the edges E are also given. You have to partition V into two disjoint subsets A and B of equal size in such a way, that the sum of the weights of the subset of edges that cross from A to B is minimized.
In the figure above, a graph containing 6 vertices , , , , , and is given. Its adjacency matrix representation is given in the center and its initial partition where cost associated with vertex a is also shown. The external cost of a is and the internal cost is . External cost means the cost of all the edges between two vertices which are in different partitions. Whereas internal cost means the cost of all the edges between two vertices which are in the same partition.
Assuming, on partition 1, the vertices are , , and . On partition 2, the vertices are d, e and f. Now, the overall cost of this partition = External cost of vertex a + External cost of vertex + External cost of vertex . But if we swap the partition of vertex with vertex , then the cost of the partition would become 18.
Dr. Bari, being a researcher was very intrigued by this challenge. He studied many books, scripts and also some ancient Egyptian scrolls on graph theory (Did you know Egyptian knew about graph around 3000 BC?). There he found a heuristic algorithm to determine an approximate partitioning (God knows why Egyptians needed to partition the graph).
But this is not enough to satisfy Dr. Bari's thirst for a better algorithm. So, he challenges you with the following task. Dr. Bari will provide you with a graph. Your task is to compute a partitioning of the graph which has a cost not more than the one found by Dr. Bari's ancient heuristic.
In the first line of input, you will take an even integer n. It denotes that there are n vertices. In the following n lines you will take a adjacency matrix as input. The -th column of the -th row indicates the weight of the edge between vertex to vertex . Weights of each edge will be at most 50.
There can be only one testcase.
The cost of vertex to vertex is always 0.
Vertices are numbered from 1 to . It means the first vertex is 1, the second vertex is 2 and the -th vertex is .
To print your computed partition, first, print "Partition 1" (without the quotes) in one line and then on the following lines print the vertex numbers of partition 1, in ascending order. After that print Partition 2 (without the quotes) in one line which will be followed by the vertex numbers of partition 2 in ascending order. Each vertex number should be printed in a new line. See the samples for a better understanding. This is a special judge problem. We will calculate your cost of partitioning and check whether it's at least as good as Dr. Bari's solution. If your algorithm is on par with Dr. Bari's, then you will get Accepted
as the verdict. Otherwise, you will get Wrong answer
as the verdict. Other verdicts may also appear based on your runtime and memory.
Input
6
0 1 2 3 2 4
1 0 1 4 2 1
2 1 0 3 2 1
3 4 3 0 4 3
2 2 2 4 0 2
4 1 1 3 2 0
Output
Partition 1:
1
3
6
Partition 2:
2
4
5