配点 : $600$ 点

ストーリー

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

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

問題文

あなたは、スタートアップの新製品として全ての惑星間を行き来出来るようなワープゲートを構築しようとしています。 惑星が $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$ 個のワープゲートの作り方を求めてください。

制約

• 入力は全て整数
• $1 \leq n \leq 18$ を満たす整数 $n$ が存在して、$N = 2^n$
• $0 \leq M \leq 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$ の間にワープゲートを作ることを表す。

4 1
3

1 0
1 3
0 2

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

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