URI Online Judge | 2052

Karnaugh Maps II

By Lucas Bucior, URI Online Judge BR Brazil

Timelimit: 2

Professor Jack delivered a list of review exercises, saying that next time will make an assessment. The main content of this list is Karnaugh Maps. John received the list, but realized he lacked the Karnaugh Maps. John is smart and knows a friend who's always going to school, and knows how to solve Karnaugh Maps. In this problem you're the friend of John, is that you can help John? Connecting the least amount possible pairs? Following the specifications of the teacher:

    1st Form pairs: one pair is connected, when you find the smaller adjacent point present.
    2nd Form isolated terms: connected pairs do not need to be connected a second time.

    In the Karnaugh Map above it is possible to identify the points connected by following the specifications of the teacher. Connected pairs: pair [2-6] indicates that the 2 point found the smaller adjacent point present 6. Isolated pairs: note that the couple [6-8] is not a pair isolated. The 6 point is connected with the 2 point, and the point 8 is connected with point 7. So it's not a valid pair. One pair is valid if, and only if, one of his points is not connected to any other point. Each pair consists of [ origin-destination ], the couple always begin to be connected to the lowest point present in the N line the entrance, origin, with the lowest adjacent destination this point, a point of origin has four destination points, for example the source point 16 is the point [ 8, 12, 14, 15 ] destination.

An instance contains an integer N. The next N rows consist of real points in the Karnaugh Map. We're talking about Karnaugh Maps of four variables. Therefore a maximum 16 numbers. As the professor showed an example, everything becomes easier. In the image above you can see that there are four pairs connected: [2-6] [7-8] [12-16] [13-14]. And all points are connected. Help John solve the review exercises.

Input

The first line of each instance contains an integer N ( 1 ≤ N ≤ 105 ), that corresponds to the number of exercises present in the list of professor Jack. The N lines contains an indefinite number of integers E ( 1 ≤ E ≤ 16 ). Each integer E indicates that the Karnaugh Map in position E, it's true, this is contains 1, as mentioned above. The entry ends with end-of-file (EOF).

Output

For each instance, print the message "Instance #H:", where H is the instance number, and growing from sequential 01. Then, for each N line of the instance, the professor asked to print, the number of pairs that are connected, the number of points not connected, followed by message "->". After, list all connected pairs in ascending order, with a space between two connected pairs. If you cannot connect any point, print the message "No connection found". Print a blank line between two consecutive instances.

Input Sample Output Sample

1
2 6 7 8 12 13 14 16
7
6 7 14
8 11 15
1 2 7 16
1 4 5 10 16
4 6 8 9 10 15
2 4 7 9 8 10 15
1 4 6 7 10 11 16 15

Instance #01:
4 0 -> 2-6 7-8 12-16 13-14

Instance #02:
1 1 -> 6-14
1 1 -> 11-15
1 2 -> 1-2
1 3 -> 1-5
3 1 -> 4-8 6-8 9-10
4 0 -> 2-4 7-8 9-10 15-7
3 4 -> 7-15 11-15 16-15