P12826 「DLESS-2」XOR and Tree Construction

一道题目需要一个题目背景。

Bob 有一棵 $n$ 个点的无根树 $T$，树上每个点都有权值，第 $i$ 个点的权值为 $a_i$。Alice 记录了一个 $n\times n$ 的矩阵 $b$，其中 $b_{i,j}$ 表示树上 $i\to j$ 最短路径上所有点的点权的异或和。 Alice 观察这个矩阵，惊奇地发现矩阵里所有数都是**正整数**。 不幸的是，某一天，Bob 把他的树搞丢了。于是你得到了 Alice 记录的矩阵，并需要还原出一种可能的树 $T$ 与序列 $a$。值得注意的是，Alice 非常靠谱，因此你总是可以还原出至少一种树。

本题有多组测试数据，第一行输入一个正整数 $T$，代表数据组数。 对于每组数据： - 第一行输入一个正整数 $n$。 - 接下来 $n$ 行，每行 $n$ 个正整数，其中第 $i$ 行第 $j$ 个数表示 $b_{i,j}$。

对于每组数据： - 第一行输出 $n$ 个数，分别代表每个点的点权 $a_1,a_2,\cdots,a_n$。 - 接下来 $n-1$ 行，每行输出两个数 $u,v$，代表有一条连接 $u,v$ 的边。

对于所有数据，保证： - $1\le T\le 10$ - $1\le n\le 500$ - $1\le b_{i,j}