You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

相遇与离别

题目描述

你打算启用你发明的新产品，它是能够来往于全部行星之间的传送门。

有 $N$ 颗行星，编号为 $0$ 到 $N-1$ ，保证存在某个 $n$ ， $N=2^n$.

为了在这些行星直线高速移动，你打算建造 $N-1$ 个可以在 $2$ 颗行星之间移动的传送门。但是，行星之间有一个缘分，在不投缘的行星之间不能连接传送门。

具体地说，不投缘的星星数列 $A=\{A_1, A_2 , \dots ,A_M\}$ 表示存在某个整数 $i$ ， $a\ \mathrm{xor}\ b\ =\ A_i$ 的情况下，并且仅在此时不能将行星 $a$ 与行星 $b$ 连接传送门。

判断是否可以是所有行星都用传送门联通（直接联通或间接联通），如果可以的话，输出一个使用最少传送门的连接方法。

$\mathrm{xor}$是指整数 $a$ 、$b$ 的每个比特的异或。

• $a$ $\mathrm{xor}$ $b$ 表示为每一位二进制不同则结果为 $1$ ，否则为 $0$ 。 例如说，$3\ \mathrm{xor}\ 5\ =\ 6$ (写成二进制为: $011\ \mathrm{xor}\ 101\ =\ 110$)。

输入格式

输入格式如下。第一行两个整数 $N,M$，接下来一行 $M$ 个整数表示 $A_i$ 。

$N$ $M$ $A_1$ $A_2$ $\cdots$ $A_M$

输出格式

如果不存在合法的连接方法，输出一个整数 $-1$；

否则输出 $N\ -\ 1$ 行，每行两个整数 $U_i,V_i$ 表示你连接的一个传送门。

样例 #1

样例输入 #1

4 1
3

样例输出 #1

1 0
1 3
0 2

数据范围

• $N\ =\ 2^n , 1\ <\ = n\ <\ =\ 18$
• $0\ <\ = M\ <\ = 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 $ ，因此是一组合法方案。