题目描述

When a competitive programmer thinks of a tree, it's not the same tree that a regural person thinks of. Luckily, in this task, both meanings are correct.

Nikola loves nature and often walks in the woods, looking at the trees and admiring their size, node degrees, paradoxically regular randomness, etc. In this day of lovely spring, there are even more reasons to look above into these magnificent creatures: the trees are full of color and that captured Nikola's attention.

So one day he observed a large tree with N nodes, seeing a color in each node. Was there a flower, an animal, or Nikola simply went mad, it's hard to say. But he was looking at that tree for a very long time, and in an N × N matrix he wrote, for each two nodes, the number of distinct colors on a unique simple path between (and including) these two nodes. Sadly, by admiring all those colors, Nikola completely forgot what the tree looked like and which colors were in the nodes.

So he needs your help. From the matrix he wrote, determine a possible tree and possible colors of the respective nodes. Colors should be denoted by numbers from {1, 2, …, N}. It is guaranteed that Nikola did not make a mistake; in other words, a solution will exist.

当一个有竞争力的程序员想到一棵树时，它和普通人想到的不是同一棵树。 幸运的是，在这项任务中，两种含义都是正确的。

尼古拉热爱大自然，经常在树林里散步，看着树木，欣赏它们的大小、节点 度数、矛盾规律的随机性等等。在这可爱的春天里，还有更多的原因 俯视这些壮丽的生物：树木色彩斑斓，捕捉到了尼古拉的 注意力。

所以有一天，他观察到一棵有 N 个节点的大树，看到每个节点都有一种颜色。有没有一朵花，一个 动物，或者尼古拉只是发疯了，很难说。但他盯着那棵树看了很久， 在一个 N × N 矩阵中，他为每两个节点写了一个唯一的不同颜色的数量 （并包括）这两个节点之间的简单路径。可悲的是，通过欣赏所有这些颜色，尼古拉 完全忘记了树的样子以及节点中的颜色。

所以他需要你的帮助。从他写的矩阵中，确定可能的树和可能的颜色 相应的节点。颜色应该用 {1, 2, ..., N} 中的数字表示。保证 尼古拉没有犯错。换句话说，将存在解决方案。

输入格式

The first line contains a subtask number (1, 2 or 3) from the Scoring section below.

The second line contains an integer N (1 ≤ N ≤ 3000), the number of nodes in the tree, which are denoted 1, 2, ..., N.

Each of the next N lines contains N integers, where j-th number in i-th line equals the number of distinct colors on the path from node i to node j.

第一行包含来自下面评分部分的子任务编号（1、2 或 3）。

第二行包含一个整数 N (1 ≤ N ≤ 3000)，树中的节点数，分别是 表示为 1、2、...、N。

接下来的 N 行中的每一行都包含 N 个整数，其中第 i 行中的第 j 个数字等于 从节点 i 到节点 j 的路径上的不同颜色。

输出格式

The first line should contain N space-separated integers between 1 and N: colors of the nodes 1, 2, ..., N.

Each of the next N – 1 lines should contain two integers A, B representing the edge (neighboring nodes) in the tree. Order of the edges and nodes inside an edge is arbitrary.

第一行应包含 N 个空格分隔的整数，介于 1 和 N 之间：节点 1、2、...、的颜色 N。

接下来的 N – 1 行中的每一行都应该包含两个整数 A，B 代表边（相邻 节点）在树中。 边和边内节点的顺序是任意的。

样例 #1

样例输入 #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

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

样例输入 #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

提示