tree

题目描述

有一个 $n$ 个节点的树，每个节点上有一个颜色 $a_i$。令 $f_{i,j}$ 表示节点 $i$ 到节点 $j$ 的路径上所有点的不同颜色数量。

现在给你一个 $n\times n$ 的二维数组 $f_{i,j}$，请你找到一个树和一个颜色方案，使其能够得到输入的 $f$ 数组。数据保证有解。

输入格式

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

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

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

输出格式

第一行输出 $n$ 个用空格分隔的整数，范围在 $1$ 到 $n$ 之间，依次表示节点 $1,2,\ldots,n$ 的颜色。

接下来输出 $n-1$ 行，每行包含两个整数 $u,v$，表示树中的一条边。边和边内节点的顺序任意。

本题为 Special Judge，只要输出任意一种合法方案即可。

样例 1 输入

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

样例 1 输出

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

样例 2 输入

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

样例 2 输出

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

数据范围与子任务