제3회 디미고 프로그래밍 챌린지 오픈 콘테스트

오늘은 디미고 신입생들이 등교하는 첫날이다. 디미고 신입생 예나의 반에는 예나를 포함해 총 2N명의 학생들이 있다. 교실에는 1번부터 2N번까지 번호가 붙은 2N개의 자리가 있으며, (2_i−1)번 자리와 2_i번 자리는 서로 붙어 있다.

예나의 반 친구들은 앞으로 앉을 자리를 학교에 먼저 도착한 순서대로 선점할 수 있다. 만약 어떤 두 학생이 (2_i−1)번과 2_i번 자리를 선택했다면, 그 둘은 짝이 된다.

학교를 오기 전 자신의 반 명단을 본 예나는 자신의 흑역사를 아주 많이 아는 채원이가 같은 반이라는 것에 충격을 받았다. 만약 예나가 채원이와 짝이 된다면 옆에서 자신을 계속 놀려댈 것이 뻔하다. 그래서 예나는 채원이와만은 짝이 되고 싶지 않다. 반대로 채원이는 예나와 짝이 되고 싶어서 안달이다.

채원이의 분노는 전교생이 두려워할 정도로 무섭기 때문에, 예나와 채원이를 제외한 다른 친구들은 두 사람이 모두 자리를 선택하기 전까지만 다음과 같은 규칙을 따른다.

• 예나가 자리를 정한 뒤엔 예나의 옆자리에 앉을 수 없다.

• 채원이가 자리를 정한 뒤엔 채원이의 옆자리에도 앉을 수 없다.

6개의 자리 중 1, 2, 5번 자리에 다른 친구들이 앉아있고 채원이가 3번 자리에 앉아있다고 생각해보자. 그렇다면 예나는 6번 자리를 선택하여 채원이와 짝이 되는 것을 피할 수 있다.

예나는 채원이와 짝이 되지 않기 위해, 채원이는 예나와 짝이 되기 위해 각자 최선을 다한다. 예나가 채원이와 짝이 되지 않도록 자리를 선택할 수 있는지를 판별하는 프로그램을 작성하시오.