问题描述

跨越路径城市的交叉口排列成网格形式。有 $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)$ 的交叉口编号为 $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