Description

给定一个非负整数矩阵 $A$，大小为 $n \times n$。对于一棵有 $n$ 个顶点的树（顶点编号为 $1$ 到 $n$），当且仅当它满足以下条件时，我们称这棵树为 冬青树：

• 对于任意两个顶点 $u$ 和 $v$（$1 \leq u, v \leq n$），矩阵中的 $A_{u,v}$ 等于从 $u$ 到 $v$ 的简单路径上所有顶点编号的按位异或和。

你的任务是构造一棵冬青树。保证至少存在一棵满足条件的冬青树。

Input Format

输入的第一行包含一个整数 $n$（$2 \leq n \leq 2000$），表示矩阵 $A$ 的大小。

接下来 $n$ 行描述矩阵 $A$。第 $i$ 行包含 $n - i + 1$ 个整数，分别是 $A_{i,i}, A_{i, i+1}, \ldots, A_{i, n}$（$0 \leq A_{i, j} < 2^{11}$）。
注意，对于所有 $1 \leq i, j \leq n$，都有 $A_{i, j} = A_{j, i}$。

保证至少存在一棵冬青树。

Output Format

输出 $n - 1$ 行，每行输出两个整数 $u$ 和 $v$（$1 \leq u, v \leq n$），表示冬青树中的一条边。

2
1 3
2

1 2

4
1 3 2 5
2 0 7
3 6
4

1 2
1 3
1 4

6
1 7 4 5 2 3
2 1 6 7 0
3 5 4 3
4 3 2
5 5
6

4 1
2 3
6 4
5 2
4 2

Hint

在第二个示例中，输出中的树如下图所示：

:::align{center} :::

该树是一棵冬青树。例如，对于顶点对 $(2, 4)$，从 $2$ 到 $4$ 的简单路径经过顶点 $2 \rightarrow 1 \rightarrow 4$，这些编号按位异或为：

这与输入中给出的 $A_{2,4} = 7$ 一致。

——翻译由 ChatGPT-5 完成