서로소 그래프 게임
면접 대비시간 제한1초메모리 제한1024 MB
간선이 없는 정점 N개에서 시작해, 두 사람이 번갈아 크기가 서로소인 두 연결 요소에 간선을 추가하고, 더 이상 둘 수 없는 사람이 진다.
문제
승민이와 찬영이는 서로소 그래프 게임을 하려고 한다. 이 게임은 간선이 없는 정점 개로 시작하며, 두 사람은 번갈아 가며 다음과 같은 규칙으로 게임을 진행한다.
- 자신의 차례에는, 연결 요소에 속한 정점의 수가 서로소인 서로 다른 두 정점을 선택해 간선을 추가해야 한다.
- 간선을 추가할 수 있는 정점 쌍이 없다면, 해당 차례의 플레이어는 패배한다.
승민이가 먼저 시작하여 두 사람 모두 최선의 전략으로 게임을 진행할 때, 누가 승리하는지 판단하자.
입력
첫째 줄에 테스트 케이스의 수 가 주어진다.
둘째 줄부터 개의 줄에 걸쳐, 각 테스트 케이스에 대해 정점의 개수 이 주어진다.
출력
각 테스트 케이스에 대해 승민이가 이긴다면 kang을, 찬영이가 이긴다면 chan을 한 줄에 하나씩 출력한다.
제한
힌트
두 정점 사이에 경로가 존재한다면, 두 정점은 연결되어 있다고 한다.
연결 요소는 내부에 속한 정점이 모두 연결된 부분 그래프이다.