← 返回题目列表

AtCoder · zone2021_f

F. 相遇与告别

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

作为你初创公司的新产品,你计划建立允许在所有行星之间旅行的曲速门。
有 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}?

按位 \mathrm{xor} 整数 a 和 b, a\ \mathrm{xor}\ b,定义如下:

  • 当 a\ \mathrm{xor}\ b 以基数 2 书写,即 2^k的地点 (k \geq 0) 是 1 如果恰好是以下之一 a 和 b is 1,和 0 否则。
例如,我们有 3\ \mathrm{xor}\ 5 = 6 (以二为基数: 011\ \mathrm{xor}\ 101 = 110).

约束

  • 输入中的所有值都是整数。
  • 存在一个整数 n 这样 1 ≤ n ≤ 18 和 N = 2^n.
  • 0 ≤ M ≤ N - 1
  • 0 < A_1 < A_2 < \dots < A_M < N

输入

输入由标准输入按以下格式给出:

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.


示例输入 1

4 1
3

示例输出 1

1 0
1 3
0 2

自从 1\ \mathrm{xor}\ 0 = 1,\ 1\ \mathrm{xor}\ 3 = 2,\ 0\ \mathrm{xor}\ 2 = 2我们可以制造那些 N - 1 跃迁门,它们允许在任意两个行星之间旅行,所以这个输出将被视为正确。
还有许多其他可能的输出也将被视为正确。


示例输入 2

8 0

示例输出 2

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

示例输入 3

8 7
1 2 3 4 5 6 7

示例输出 3

-1