2486번 - 그레이 코드 스페셜 저지

이진 코드 중에서 모든 인접한 코드가 한 비트만 서로 다르면 그레이(Gray) 코드라고 말한다. 첫째 코드와 마지막 코드도 인접하다고 보고 한 비트만 달라야 한다. 아래에 3-비트 그레이 코드가 있다. 첫 번째 코드와 둘째 코드, 둘째와 셋째, …, 그리고 마지막 코드 100은 첫째 코드 000과 1비트만 다르다.

000 - 001 - 011 - 010 - 110 - 111 - 101 - 100

그레이 코드에서, 111과 한 비트가 다른 110, 101은 코드에서 인접하게 나타나지만, 역시 한 비트가 다른 011은 그렇지 않다. 이 사실을 관찰한 철희군은 111과 011이 인접한 그레이 코드가 존재하는가 하는 문제에 호기심이 발동하였고, 그런 코드가 있다는 것을 손으로 확인하였다. 비트 수가 더 큰 경우에는 손으로 확인하기가 어려워, 컴퓨터 프로그램을 작성하기로 하였다.

한 비트가 다른 쌍들이 하나 혹은 둘 주어질 때, 그 쌍이 인접하다는 조건을 만족하는 그레이 코드가 존재하는가를 확인하고, 존재하면 조건을 만족하는 그레이 코드를 출력하는 프로그램을 작성하라.  

첫째 줄에 코드에서 비트의 수를 나타내는 M(3 ≤ M ≤ 15)과 인접해야 하는 코드 쌍의 수 K(1 ≤ K ≤ 2)가 주어진다. 이어서 K개의 줄에 한 줄에 하나씩 인접하기를 원하는 코드 쌍이 빈칸을 사이에 두고 입력된다.

첫째 줄에 조건을 만족하는 그레이 코드가 존재하면, 그레이 코드를 000…0부터 시작하여 차례로 한 줄에 코드 8개씩 2^M-3 줄에 걸쳐서 출력한다. 만일 답이 여럿일 경우에는 그 중 하나만 출력하면 된다. 조건을 만족하는 그레이 코드가 존재하지 않으면 -1을 출력한다.