/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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 個のワープゲートの作り方を求めてください。
\mathrm{xor} とは
整数 a, b のビットごとの排他的論理和 a\ \mathrm{xor}\ b は、以下のように定義されます。
- a\ \mathrm{xor}\ b を二進表記した際の 2^k (k \geq 0) の位の数は、a, b を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
制約
- 入力は全て整数
- 1 ≤ n ≤ 18 を満たす整数 n が存在して、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
Score : 600 points
Problem Statement
As your startup's new product, you are planning to build warp gates that allow travel between all planets.
There are N planets, numbered 0 through N-1, where there is an integer n such that N = 2^n. To allow fast travel between all these planets, you want to make N - 1 warp gates, each of which allows instant travel between two planets. However, for some pairs of planets that are incompatible with each other, you cannot make a warp gate between them.
More specifically, such pairs of planets incompatible with each other are represented by a sequence A = (A_1, A_2, \dots, A_M). If and only if there is an integer i such that a\ \mathrm{xor}\ b = A_i, you cannot make a warp gate between Planet a and Planet b.
Determine whether it is possible to make a network of warp gates allowing travel between every two planets. If it is possible, find one such way to make N - 1 warp gates.
What is \mathrm{xor}?
The bitwise \mathrm{xor} of integers a and b, a\ \mathrm{xor}\ b, is defined as follows:
- When a\ \mathrm{xor}\ b is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if exactly one of a and b is 1, and 0 otherwise.
Constraints
- All values in input are integers.
- There exists an integer n such that 1 ≤ n ≤ 18 and N = 2^n.
- 0 ≤ M ≤ N - 1
- 0 < A_1 < A_2 < \dots < A_M < N
Input
Input is given from Standard Input in the following format:
N M A_1 A_2 \cdots A_M
Output
If it is impossible to make a network of warp gates allowing travel between every two planets, print -1.
If it is possible to make such a network, print one way to make such N - 1 warp gates in the following format:
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}
It means you make a warp gate between Planet U_i and Planet V_i.
Sample Input 1
4 1 3
Sample Output 1
1 0 1 3 0 2
Since 1\ \mathrm{xor}\ 0 = 1,\ 1\ \mathrm{xor}\ 3 = 2,\ 0\ \mathrm{xor}\ 2 = 2, we can make those N - 1 warp gates, and they allow travel between every two planets, so this output will be considered correct.
There are many other possible outputs that will also be considered correct.
Sample Input 2
8 0
Sample Output 2
1 0 1 3 1 5 6 7 6 4 6 2 3 2
Sample Input 3
8 7 1 2 3 4 5 6 7
Sample Output 3
-1