Limits 10s, 512 MB · Custom Checker

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 aa, bb, cc, dd, ee, and ff 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 3+2+4=93+2+4 = 9 and the internal cost is 1+2=31+2=3. 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 aa, bb, and cc. 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 bb + External cost of vertex c=(3+2+4)+(4+2+1)+(3+2+1)=22c = (3+2+4) + (4+2+1) + (3+2+1) = 22. But if we swap the partition of vertex bb with vertex ff, 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.

Input

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 n×nn \times n adjacency matrix as input. The jj-th column of the ii-th row indicates the weight of the edge between vertex ii to vertex jj. Weights of each edge will be at most 50.

6n10246 ≤ n ≤ 1024

There can be only one testcase.

The cost of vertex ii to vertex ii is always 0.

Vertices are numbered from 1 to nn. It means the first vertex is 1, the second vertex is 2 and the nn-th vertex is nn.

Output

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.

Example

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

Submit

Login to submit.

Statistics

60% Solution Ratio
Prof_ChaosEarliest, May '18
nusuBotFastest, 0.8s
Prof_ChaosLightest, 1.2 MB
Prof_ChaosShortest, 2093B
Toph uses cookies. By continuing you agree to our Cookie Policy.