By Lucas Bucior, URI Online Judge Brazil
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:
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.
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).
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|