AT_zone2021_f 出会いと別れ

你打算作为一家初创公司的新产品，构建能够在所有行星之间自由往返的“跃迁门”。 共有 $N$ 个行星，编号为 $0$ 到 $N-1$。这里存在一个整数 $n$，使得 $N=2^n$。为了能在这些行星之间高速移动，你需要建立 $N-1$ 个跃迁门，每个门可以让两颗行星之间瞬间移动，并希望通过这些门让所有行星之间都能互相到达。然而，行星之间存在“相性”，对于相性不好的行星对，无法建立跃迁门。 具体来说，相性不好的行星对由数列 $A=(A_1,A_2,\dots,A_M)$ 给出。若存在某个整数 $i$，使得 $a\ \mathrm{xor}\ b = A_i$，则且仅当此时，不能在行星 $a$ 和行星 $b$ 之间建立跃迁门。 请判断是否可以构建一个让所有行星间都能互相到达的跃迁门网络。如果可以，请给出 $N-1$ 个跃迁门的建立方式。 $\mathrm{xor}$ 是指整数 $a,b$ 的按位异或运算 $a\ \mathrm{xor}\ b$，定义如下： - $a\ \mathrm{xor}\ b$ 的二进制表示中，第 $2^k$ 位（$k\geq 0$）的数，如果 $a$ 和 $b$ 的二进制表示中该位只有一个为 $1$，则为 $1$，否则为 $0$。 例如，$3\ \mathrm{xor}\ 5 = 6$（二进制表示为：$011\ \mathrm{xor}\ 101 = 110$）。

输入通过标准输入按以下格式给出。 > $N$ $M$ $A_1$ $A_2$ $\cdots$ $A_M$

如果无法构建让所有行星间都能互相到达的跃迁门网络，输出 `-1`。 如果可以，请输出 $N-1$ 个跃迁门的建立方式，格式如下： > $U_1$ $V_1$ > $U_2$ $V_2$ > $\vdots$ > $U_{N-1}$ $V_{N-1}$ 表示在行星 $U_i$ 和行星 $V_i$ 之间建立一个跃迁门。

### 故事背景 当你爬上梯子进入 UFO 时，发现被捕的穆尔和一位面目狰狞的外星人正等着你。但更引人注目的是，那堆你熟悉的罐头堆积如山。没错，那绝对是 ZONe mad\_hacker ver.1.0.0。而且既然外星人也在喝 mad\_hacker，那他肯定也是在其他星球上努力“MADHACKING”的工程师，我确信无疑。像在技术交流会上第一次和陌生人搭话一样，我有些紧张地开口了。 “……foo” 外星人的眼睛立刻亮了起来。 “……bar!” “fizz!”“buzz!” 黑客们的灵魂跨越星辰交汇在一起。我们一拍即合，彻夜畅谈各自星球的语言和编程范式。被外星人看中并当场招募，我成为了首位在银河系初创公司工作的地球人。再见了，地球。谢谢你，ZONe mad\_hacker。你好，宇宙！ ### 约束条件 - 所有输入均为整数。 - 存在整数 $n$ 满足 $1 \leq n \leq 18$，且 $N=2^n$。 - $0 \leq M \leq N-1$。 - $0 < A_1 < A_2 < \dots < A_M < N$。 ### 样例解释 1 由于 $1\ \mathrm{xor}\ 0 = 1$，$1\ \mathrm{xor}\ 3 = 2$，$0\ \mathrm{xor}\ 2 = 2$，因此可以建立跃迁门，并且通过 $N-1$ 个跃迁门可以让所有行星间互相到达，所以这是正确答案。其他正确输出也有很多种。 由 ChatGPT 4.1 翻译