The Sadness of Division

Time limit1sMemory limit512 MB

Summary

Split N members into two camps, respecting fixed members, to minimize the total weight of pairs split across camps, and output the lexicographically smallest camp A.

Level: Medium7 of 10
Topics: Graph, Minimum spanning tree, Greedy, Implementation
Solved: No attempts yet

Problem

A club has $N$ members. An old argument has split the club into camp A and camp B. Every member belongs to exactly one camp, and nobody belongs to both.

If member $i$ and member $j$ belong to different camps, that pair creates sadness $w[i][j]$ . Some members hold their position so firmly that they must join camp A, and some must join camp B. Others do not care which camp they join.

Divide the $N$ members between the two camps so that the total sadness is minimal.

Input

The first line contains the number of members $N$ ( $1 \le N \le 500$ ).

The second line contains $N$ integers. If the $i$ -th number is 1, member $i$ must join camp A; if it is 2, member $i$ must join camp B; if it is 0, member $i$ may join either camp.

Each of the next $N$ lines contains $N$ integers. The $j$ -th number on line $i+2$ is $w[i][j]$ . The input always satisfies $w[i][j] = w[j][i]$ and $w[i][i] = 0$ , and every $w[i][j]$ is a non-negative integer no larger than 1000.

Output

Print the minimum total sadness on the first line.

On the second line print the numbers of the members in camp A in increasing order, separated by single spaces. On the third line print the numbers of the members in camp B the same way. If a camp holds nobody, print an empty line for it.

Several divisions can reach the minimum total sadness, so only one of them counts as correct. Put a member in camp A only if that member belongs to camp A in every division that reaches the minimum, and put everyone else in camp B. The division built this way also reaches the minimum total sadness, and its camp A is contained in the camp A of every other minimal division, so exactly one division satisfies the rule.

Examples8

Example 1

Input

Expected output

4
2
1 3 4 5

Example 2
Input
```
1
0
0
```
Expected output
```
0

1
```
Example 3
Input
```
1
1
0
```
Expected output
```
0
1
```
Example 4
Input
```
2
0 0
0 5
5 0
```
Expected output
```
0

1 2
```
Example 5
Input
```
2
1 2
0 7
7 0
```
Expected output
```
7
1
2
```

Example 6

Input

Expected output

0
1
2 3 4

Example 7
Input
```
3
1 0 2
0 100 0
100 0 1
0 1 0
```
Expected output
```
1
1 2
3
```

Example 8

Input

Expected output

10
1
2 3 4