题目描述

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$ 的边。

2
3
1 3 7
3 2 6
7 6 4
5
8 9 10 15 1 
9 1 2 14 9 
10 2 3 13 10 
15 14 13 7 6 
1 9 10 6 8

1 2 4 
1 2
2 3
8 1 3 7 8 
1 2
1 4
2 3
2 5

1
2
10000000000 29999508480
29999508480 20000000000

10000000000 20000000000
1 2

说明/提示

对于所有数据，保证：

• $1\le T\le 10$
• $1\le n\le 500$
• $1\le b_{i,j}<2^{60}$