P11337 [COI 2019] IZLET

**译自 [COI 2019](https://hsin.hr/coci/archive/2018_2019/) T1「[IZLET](https://hsin.hr/coci/archive/2018_2019/olympiad_tasks.pdf)」** 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$ 间有一条边。

对于 $100\%$ 的数据，保证 $1\le N\le 3000$。 | 子任务编号 $T$ | 分值 | 特殊性质 | |:-:|:-:|:-:| | $1$ | $18$ | 矩阵中的数均不超过 $2$ | | $2$ | $25$ | 存在一组解使得树的结构是一条链，每个节点 $i(1\le i