{"raw_statement":[{"iden":"problem statement","content":"As your startup's new product, you are planning to build warp gates that allow travel between all planets.  \nThere 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.  \nMore 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$.  \nDetermine 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.\nWhat is $\\mathrm{xor}$?The bitwise $\\mathrm{xor}$ of integers $a$ and $b$, $a\\ \\mathrm{xor}\\ b$, is defined as follows:\n\n*   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.\n\nFor example, we have $3\\ \\mathrm{xor}\\ 5 = 6$ (in base two: $011\\ \\mathrm{xor}\\ 101 = 110$)."},{"iden":"constraints","content":"*   All values in input are integers.\n*   There exists an integer $n$ such that $1 ≤ n ≤ 18$ and $N = 2^n$.\n*   $0 ≤ M ≤ N - 1$\n*   $0 < A_1 < A_2 < \\dots < A_M < N$"},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $A_2$ $\\cdots$ $A_M$"},{"iden":"sample input 1","content":"4 1\n3"},{"iden":"sample output 1","content":"1 0\n1 3\n0 2\n\nSince $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.  \nThere are many other possible outputs that will also be considered correct."},{"iden":"sample input 2","content":"8 0"},{"iden":"sample output 2","content":"1 0\n1 3\n1 5\n6 7\n6 4\n6 2\n3 2"},{"iden":"sample input 3","content":"8 7\n1 2 3 4 5 6 7"},{"iden":"sample output 3","content":"\\-1"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}