You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

译自 COI 2019 T1「IZLET」

Nikola 在观察一棵树。这是一颗 $N$ 个节点的树，每个节点有一个颜色，颜色在 $1$ 到 $N$ 之间。Nikola 记录下了这样一个 $N \times N$ 的矩阵：

矩阵的第 $i$ 行第 $j$ 列表示，节点 $i$ 到节点 $j$ 的路径上总共出现的颜色的数量。

现在 Nikola 只记得这个矩阵，而忘记了树的具体信息！现在他把这个矩阵告诉你，请你找出一棵树并且给每个节点标上颜色，使得符合矩阵记录的信息。

Nikola 的记录和记忆都是正确的，所以你至少能找出一种合法的方案。

输入格式

第一行输入一个正整数 $T$ 表示数据类型。

第二行输入一个正整数 $N$ 表示节点数。

接下来输入共 $N$ 行，每行 $N$ 个正整数，即输入 Nikola 记录下的矩阵。

输出格式

第一行输出 $N$ 个正整数，表示每个节点的颜色。

接下来输出 $N - 1$ 行，每行两个正整数 $A,B$ 表示节点 $A,B$ 间有一条边。

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 2 3 4 4
1 2
1 3
1 4
2 5

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

1 2 3 2
1 2
2 3
3 4

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

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

提示

对于 $100\%$ 的数据，保证 $1\le N\le 3000$。