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 翻译