题目描述

あなたは、スタートアップの新製品として全ての惑星間を行き来出来るようなワープゲートを構築しようとしています。
惑星が $N$ 個あり、$0$ から $N\ -\ 1$ までの番号がついています。ここで、ある整数 $n$ が存在して、$N\ =\ 2^n$ です。これらの惑星の間を高速に移動するために、$2$ 惑星間を瞬時に移動出来るワープゲートを $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$ を二進表記した際の $2^k$ の位の数のうち一方のみが $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$ の間にワープゲートを作ることを表す。

题目大意

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

有 $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$ 。

4 1
3

1 0
1 3
0 2

8 0

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

8 7
1 2 3 4 5 6 7

-1

提示

ストーリー

梯子を登りきり UFO に入ると、そこには捕らえられたムーアと、恐ろしい形相の宇宙人が待ち構えていた。 しかしそれ以上に、見覚えのある缶がうずたかく積まれているのが目に留まった。 間違いない。あれは間違いなく ZONe mad_hacker ver.1.0.0 だ。 そして mad_hacker を飲んでいるということは、この宇宙人も別の星で MADHACKING に勤しむエンジニアに違いない、と俺は確信した。 勉強会で初めての相手に話しかける時の如く、俺はやや緊張しながら口を開いた。
「...foo」
聞くや否や、宇宙人の目が輝いた。
「...bar!」

「fizz!」「buzz!」
ハッカーたちの魂が、星を超えて交わった。 すっかり意気投合した俺たちは、それぞれの星の言語やプログラミングパラダイムについて一晩中語り明かした。 気に入られ、その場でスカウトされた俺は地球人として初のミルキーウェイ(天の川)のスタートアップで働くことになったのだった。 さようなら、地球。ありがとう、ZONe mad_hacker。そして、hello, space!

制約

• 入力は全て整数
• $1\ <\ = n\ <\ =\ 18$ を満たす整数 $n$ が存在して、$N\ =\ 2^n$
• $0\ <\ = M\ <\ = N\ -\ 1$
• $0\ <\ A_1\ <\ A_2\ <\ \dots\ <\ A_M\ <\ N$

Sample Explanation 1

$ 1\ \mathrm{xor}\ 0\ =\ 1,\ 1\ \mathrm{xor}\ 3\ =\ 2,\ 0\ \mathrm{xor}\ 2\ =\ 2 $ であるためワープゲートを作ることができ、$N\ -\ 1$ 個のワープゲートで全ての惑星間を行き来できるようになっているので、正解となります。 正解となる出力は他にも多数あります。