그레이 코드

M비트 이진 문자열 2^M개를 모두 한 번씩 나열하되, 이웃한 두 문자열이 정확히 한 비트만 다르면 그 나열을 순환 그레이 코드라고 한다. 마지막 문자열과 첫 번째 문자열도 이웃으로 보며, 두 문자열은 한 비트만 달라야 한다. 3비트에서는 000, 001, 011, 010, 110, 111, 101, 100 순서가 이런 코드가 될 수 있다.

어떤 문자열은 한 비트만 다른 문자열이 여러 개 있다. 그러나 주어진 순환 그레이 코드 안에서 실제로 이웃하는 문자열은 그중 두 개뿐이다.

한 비트만 다른 문자열 쌍이 하나 또는 두 개 주어진다. 모든 주어진 쌍이 서로 이웃하도록 하는 순환 그레이 코드가 존재하는지 판단하고, 존재하면 그런 코드를 하나 출력하라.

첫째 줄에 코드의 비트 수 M과 이웃해야 하는 문자열 쌍의 수 K가 주어진다.

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

다음 K개 줄에는 이웃해야 하는 두 M비트 이진 문자열이 공백으로 구분되어 주어진다. 각 쌍의 두 문자열은 정확히 한 비트만 다르다.

조건을 만족하는 순환 그레이 코드가 존재하면, 00...0부터 시작하여 모든 코드를 순서대로 출력한다. 한 줄에는 코드 8개를 공백으로 구분해 출력하므로 전체 출력은 2^(M-3)줄이다. 가능한 답이 여러 개라면 아무거나 하나만 출력해도 된다.

조건을 만족하는 코드가 존재하지 않으면 -1을 출력한다.