当算法竞赛选手想到“树”时，他们脑海中浮现的树与普通人所想的树并不相同。幸运的是，在这道题中，这两种含义都是正确的。

Nikola 热爱大自然，经常在森林里散步，观察树木并赞叹它们的大小、节点度数、奇妙的规则随机性等。在这个美丽的春日里，有更多的理由去仰望这些宏伟的造物：树木色彩斑斓，这吸引了 Nikola 的注意。

于是有一天，他观察了一棵拥有 $N$ 个节点的巨大树木，并看到了每个节点上的颜色。很难说那是一朵花、一只动物，还是 Nikola 只是单纯地疯了，这很难说。但他在那棵树前看了很久，并在一个 $N \times N$ 的矩阵中记录了每两个节点之间（包括这两个节点本身）唯一简单路径上不同颜色的数量。不幸的是，由于沉浸在欣赏这些色彩中，Nikola 完全忘记了这棵树长什么样，以及各个节点上分别是什么颜色。

因此，他需要你的帮助。根据他写下的矩阵，确定一棵可能的树以及各个节点上可能的一种颜色方案。颜色应该用 $\{1, 2, \dots, N\}$ 中的数字表示。保证 Nikola 没有犯错；换句话说，一定存在解。

输入格式

第一行包含一个子任务编号（$1$、$2$ 或 $3$），对应下方“子任务”部分。

第二行包含一个整数 $N$（$1 \le N \le 3000$），表示树中节点的数量，节点编号为 $1, 2, \dots, N$。

接下来的 $N$ 行，每行包含 $N$ 个整数，其中第 $i$ 行的第 $j$ 个数字表示从节点 $i$ 到节点 $j$ 的路径上不同颜色的数量。

输出格式

第一行应包含 $N$ 个由空格隔开的介于 $1$ 和 $N$ 之间的整数：表示节点 $1, 2, \dots, N$ 的颜色。

接下来的 $N - 1$ 行，每行应包含两个整数 $A$ 和 $B$，表示树中的一条边（相邻节点）。边与边之间的顺序以及一条边中两个节点的顺序是任意的。

子任务

样例

输入样例 1

3
5
1 2 2 2 3
2 1 3 3 2
2 3 1 3 4
2 3 3 1 3
3 2 4 3 1

输出样例 1

1 2 3 4 4
1 2
1 3
1 4
2 5

输入样例 2

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

输出样例 2

1 2 3 2
1 2
2 3
3 4

输入样例 3

1
5
1 2 2 2 2
2 1 1 2 2
2 1 1 2 2
2 2 2 1 2
2 2 2 2 1

输出样例 3

1 2 2 1 2
1 2
2 3
2 4
1 5