Under construction

Still being built. Things may change

Jigsaw Puzzle

Time limit2sMemory limit512 MB

Summary
Assemble n jigsaw pieces, rotation allowed but not flipping, so matching irregular edges meet and straight edges form the border of an h by w rectangle, or report impossible.
Level

Medium6 of 10

Topics
Implementation, Hash map, Math
Solved
No attempts yet

Problem

You found a box with old games when cleaning up your attic, and among them was also a jigsaw puzzle. Unfortunately, the packaging was damaged, so a couple of puzzle pieces are scattered around the bottom of the box, and you suspect that some of the pieces may have been lost elsewhere. Some of the pieces may even come from an entirely different puzzle. Now you have a pile of puzzle pieces in front of you, and you must assemble them into a solved puzzle.

Figure J.1: Illustration of the first sample.

More formally:

  • There are n square pieces, numbered from 1 to n. They must be arranged side by side to form a single rectangle. All n pieces must be used.
  • The edges of the pieces are either straight or irregular. Straight edges must be placed on the boundary of the rectangle, and irregular edges must be placed on the inside.
  • The irregular edges are all shaped differently, so each edge shape occurs exactly two times, on two different pieces. Two pieces can be placed next to each other only if the shapes of their corresponding edges match.
  • You may rotate the pieces, but you may not flip them over.

Input

The first line contains one integer n (1 is at most n is at most 3 times 10^5), the number of pieces. Each of the next n lines contains four integers, giving the connections (edge shapes) of the corresponding piece in counter-clockwise order.

A connection of type 0 stands for a straight edge. The other connection types are numbered with consecutive positive integers starting from 1, and each of them occurs exactly two times, on two different lines.

Output

If the pieces cannot be assembled as described above, output impossible. Otherwise, output the solved puzzle in the following format:

  • One line with two integers h and w (h, w is at least 1, h times w = n), the height and width of the grid.
  • h lines, each with w integers, giving the numbers of the pieces.

Any rotation of the correct solution will be accepted.

Examples2

  1. Example 1

    Input
    6
0 0 1 6
0 7 4 0
0 0 2 1
5 3 0 6
3 7 0 0
4 5 2 0
    Expected output
    2 3
1 4 5
3 6 2

  2. Example 2

    Input
    4
0 0 1 2
0 0 2 3
0 0 3 4
0 0 1 4
    Expected output
    impossible