13034번 - 다각형 게임 분류

N개의 꼭짓점으로 이루어진 볼록 다각형이 있다. 다각형의 내각은 모두 180보다 작다. 꼭짓점은 1부터 N번까지 시계 방향으로 번호가 매겨져 있다.

성관이와 홍준이는 다각형에서 게임을 하려고 한다. 성관이가 먼저 턴을 갖는다.

각 턴마다 플레이어는 두 꼭짓점을 고르고, 선분을 긋는다 (변과 일치해도 된다). 이때, 이미 그려져 있는 선분과 교차하면 안 된다 (선분의 끝 점에서 겹치는 것도 교차하는 것이다). 더 이상 선분을 그릴 수 없는 사람이 게임을 패배한다.

N이 주어진다. 두 사람이 최적의 방법으로 게임했을 때, 누가 이기는지 구하는 프로그램을 작성하시오.

첫째 줄에 N (3 ≤ N ≤ 1,000) 이 주어진다.

성관이가 이기면 1, 홍준이가 이기면 2를 출력한다.