← 返回题目列表

AtCoder · jag2017summer_day3_c

C. 忍者地图

中文机器翻译题面 查看原题

问题陈述

交叉路径城市的交叉点与网格对齐。东西向有$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