그레이 코드

이진 코드 중에서 모든 인접한 코드가 한 비트만 서로 다르면 그레이(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을 출력한다.

예제1

예제2

출처

KOI 본선 2010 고5

그레이 코드 1초 256MB