问题陈述
交叉路径城市的交叉点与网格对齐。东西向有$N$条街道,从北到南编号为1到$N$。 还有$N$南北走向的街道,从西到东编号为1到$N$。 每对东西向和南北向的街道都有一个交叉口;因此有 $N^2$ 个交叉点,编号从 1 到 $N^2$。
令人惊讶的是,这座城市的所有居民都是忍者。为了防止外人知道他们的位置,交叉口的编号被打乱了。
您知道交叉点之间的连接,并尝试从信息中推断出它们的位置。如果有多于一组可能的位置,您可以输出其中任何一个。
输入
输入由单个测试用例组成,格式如下。
$N$ $a_1\b_1$ $\cdots$ $a_{2N^2-2N} \ b_{2N^2-2N}$
第一行由整数 $N \ (2 \le N \le 100)$ 组成。 以下 $2N^2-2N$ 线表示交叉点之间的连接。 第$(i+1)$行由两个整数$a_i$和$b_i$组成($1 \le a_i, b_i \le N^2$, $a_i \ne b_i$),表示第$a_i$和第$b_i$交点相邻。更准确地说,我们用 $(r, c)$ 表示第 $r$ 个东西向街道和第 $c$ 个南北向街道的交叉点。 如果对于某些 $r$ 和 $c$,$(r, c)$ 的交集数为 $a_i$,则 $(r - 1, c)$、$(r + 1, c)$、$(r, c - 1)$ 或 $(r, c + 1)$ 的交集数必须为 $b_i$。 邻接的所有输入都是不同的,即 $(a_i,b_i)\ne(a_j,b_j)$ 和 $(a_i,b_i)\ne(b_j,a_j)$ 对于所有 $1 \le i < j \le 2N^2-2N$。这意味着您将获得网格上所有邻接点的信息。
输入保证描述有效的地图。
输出
打印一组可能的交点位置。 更准确地说,输出由 $N$ 行组成,每行都有空格分隔的 $N$ 整数。 第$r$行的第$c$个整数应该是$(r, c)$的交集数。
如果有多于一组可能的位置,则可以输出其中任何一个。
示例输入 1
3 1 2 4 7 8 6 2 3 8 9 5 3 4 6 5 6 7 8 1 4 2 6 5 9
样本输入 1 的输出
7 4 1 8 6 2 9 5 3
以下输出也将被接受。
1 2 3 4 6 5 7 8 9
示例输入 2
4 12 1 3 8 10 7 13 14 8 2 9 12 6 14 11 3 3 13 1 10 11 15 4 15 4 9 14 10 5 7 2 5 6 1 14 5 16 11 15 6 15 13 9 6 16 4 13 2
样本输入 2 的输出
8 2 5 7 3 13 14 10 11 15 6 1 16 4 9 12