육각 격자를 고리 모양으로 감은 뒤 nm/4마리의 벌이 각자 자기와 이웃 3개를 지배해 모든 꼭짓점을 덮을 수 있는지 판정한다.
어려움8수학조합론구현완전 탐색아직 제출이 없습니다시간 제한2초메모리 제한512 MB토성 벌(Apis saturnii)은 벌집을 고리 모양으로 짓는다. 벌집은 육각형 격자이고, 벽을 간선으로 벽이 만나는 지점을 정점으로 삼아 그래프로 나타낸다. 육각형을 조금 눌러 1×2 직사각형으로 만들면 모든 정점에 정수 좌표를 붙일 수 있다. 이때 정점 (i,j)는 (i,j−1), (i,j+1)과 인접하고, i+j가 홀수면 (i+1,j)와, i+j가 짝수면 (i−1,j)와 인접한다.
n×m 격자를 고리로 만들려면 가장자리를 이어 붙인다. n과 m이 모두 짝수면 끝점이 (n,j)인 간선은 (0,j)에서 끝나고, 끝점이 (i,m)인 간선은 (i,0)에서 끝난다. 둘 중 하나가 홀수면 양쪽이 맞물리도록 격자를 비틀어 붙인다. n이 홀수면 (n,j)는 (0,j+1)이 되고, m이 홀수면 (i,m)은 (i+1,0)이 된다. 무리의 정신은 악수 보조정리를 알고 있어서 n과 m이 모두 홀수인 벌집은 짓지 않는다. 그림 A.1에 벌집의 예가 있다.

그림 A.1: 벌집의 예
병정벌은 정점 하나에 앉아 그 정점과 그에 인접한 정점 3개를 지킨다. 무리의 정신은 벌집 전체를 지키려면 nm/4마리가 필요하다는 사실을 알고 있고, 무리에는 정확히 그만큼의 병정벌이 있다. 그런데 지키기 까다로운 벌집이 있어서 토성 벌은 그런 곳에 살지 않는다.
벌집이 무리가 살기에 알맞은 곳인지 판정하라.
첫째 줄에 정수 n과 m이 주어진다 (2≤m,n≤10000). n과 m 중 적어도 하나는 짝수다.
n×m 벌집을 nm/4마리가 지킬 수 있으면 possible을, 그렇지 않으면 impossible을 출력한다. nm이 4로 나누어떨어지지 않으면 무리를 꾸릴 수 없으므로 impossible을 출력한다.