Gray Code

A cyclic Gray code is an ordering of all 2^M binary strings of length M such that every two neighboring strings differ in exactly one bit. The last string and the first string are also considered neighbors, so they must differ in exactly one bit as well. For 3 bits, 000, 001, 011, 010, 110, 111, 101, 100 is one possible cyclic Gray code.

A string can differ by one bit from several other strings, but only two of them are its actual neighbors in a particular cyclic Gray code.

You are given one or two pairs of binary strings that differ in exactly one bit. Determine whether there is a cyclic Gray code in which every given pair is neighboring, and output one such code if it exists.

The first line contains M, the number of bits in each code, and K, the number of required neighboring pairs.

• 3 <= M <= 15
• 1 <= K <= 2

Each of the next K lines contains two M-bit binary strings separated by a space. The two strings in each pair differ in exactly one bit.

If a cyclic Gray code satisfying the conditions exists, output all codes in order, starting with 00...0. Print 8 codes per line, separated by spaces, so the output has 2^(M-3) lines. If there are multiple valid answers, output any one of them.

If no such code exists, output -1.