P12826 「DLESS-2」XOR and Tree Construction

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

Bob has an unrooted tree $T$ with $n$ vertices. Each vertex has a weight, with the weight of vertex $i$ being $a_i$. Alice has recorded an $n \times n$ matrix $b$, where $b_{i,j}$ is the XOR sum of the weights of all vertices on the shortest path from vertex $i$ to vertex $j$. Alice observed this matrix and, to her surprise, found that all its elements are **positive integers**. Unfortunately, one day, Bob lost his tree. Now, you are given Alice's matrix $b$, and your task is to reconstruct a possible tree $T$ and the sequence of weights $a$. It is worth noting that Alice is very reliable, so it is guaranteed that at least one such tree can always be reconstructed.

The input consists of multiple test cases. The first line contains a single positive integer $T$, representing the number of test cases. For each test case: - The first line contains a positive integer $n$. - The next $n$ lines describe the matrix $b$. The $j$-th integer on the $i$-th of these lines is $b_{i,j}$.

For each test case: - In the first line, output $n$ integers, representing the vertex weights $a_1, a_2, \ldots, a_n$. - Then, output $n-1$ lines. Each line should contain two integers $u,v$, representing an edge between vertex $u$ and vertex $v$.

For all test data, it is guaranteed that: - $1\le T\le 10$ - $1\le n\le 500$ - $1\le b_{i,j}