410452: GYM104022 J Let's Play Jigsaw Puzzles!

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?

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 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.

2
-1 3 -1 2
-1 4 1 -1
1 -1 -1 4
2 -1 3 -1

1 2
3 4