410452: GYM104022 J Let's Play Jigsaw Puzzles!

Memory Limit:512 MB Time Limit:4 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

J. Let's Play Jigsaw Puzzles!time limit per test4 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

Bob bought a new jigsaw puzzle yesterday. The puzzle consists of $$$m^2$$$ rectangular pieces, where each piece contains a unique number ranged from $$$1$$$ to $$$m^2$$$ used for identification and four associated numbers indicating the adjacent pieces.

Specifically, the piece numbered $$$i$$$ is described with four numbers $$$n_i$$$, $$$s_i$$$, $$$w_i$$$ and $$$e_i$$$, corresponding to four adjacent pieces: the piece numbered $$$n_i$$$ (resp., $$$s_i$$$, $$$w_i$$$ and $$$e_i$$$) lie on the north side (resp., south side, west side and east side). If an associated number is $$$-1$$$, no more piece would lie on the corresponding side.

Undoubtedly, the goal of this game is to arrange all pieces in the correct locations. The instruction says that the complete image is square, with $$$m$$$ rows and $$$m$$$ columns.

At this juncture, Bob is at the International Collegiate Programming Contest in Yinchuan. He has no time to solve the jigsaw puzzle but has to solve Problem K instead. Can you help him?

Input

The first line contains an integer $$$m$$$ $$$(1 \leq m \leq 10^3)$$$.

In the next $$$m^2$$$ lines, the $$$i$$$-th line contains four integers $$$n_i$$$, $$$s_i$$$, $$$w_i$$$ and $$$e_i$$$ $$$(n_i, s_i, w_i, e_i \in \{-1\} \cup [1, m^2])$$$. It is guaranteed that a corresponding solution does exist.

Output

Output a sorted jigsaw puzzle in $$$m$$$ lines from north to south, where each line contains $$$m$$$ integers representing the pieces from west to east in the corresponding row of the jigsaw puzzle.

ExampleInput
2
-1 3 -1 2
-1 4 1 -1
1 -1 -1 4
2 -1 3 -1
Output
1 2
3 4

加入题单

上一题 下一题 算法标签: