题目描述

译自 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$ 间有一条边。

样例 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 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$。