모그는 두 마리의 하늘다람쥐가 파는 굴을 연구한다. 땅은 크기가 인 격자이다. 각 칸은 좌표 로 나타낸다. 두 칸이 한 좌표에서만 만큼 다르면 두 칸은 면으로 인접한다.
첫째 하늘다람쥐는 에서, 둘째 하늘다람쥐는 에서 굴을 파기 시작한다. 두 시작점은 서로 다르다. 각 하늘다람쥐의 굴은 다음 조건을 만족해야 한다.
칸 하나로 이루어진 굴도 허용한다. 두 굴은 같은 칸을 공유할 수 없다.
모든 칸이 두 굴 중 정확히 하나에 속하도록 나눌 수 있는지 판단하고, 가능하다면 그러한 배치 하나를 출력하여라.
입력은 다음과 같은 형식으로 주어진다.
각 테스트 케이스마다 조건을 만족하는 배치가 없다면 NO를 한 줄에 출력한다.
배치가 있다면 먼저 YES를 한 줄에 출력한다. 그다음 개의 줄에 걸쳐 각 줄에 개의 정수를 출력한다. 순서로, 각 에 대해 순서로 한 줄씩 출력한다. 해당 줄의 번째 정수는 가 첫째 굴에 속하면 , 둘째 굴에 속하면 여야 한다.
는 테스트 케이스의 수이다. 각 케이스는 다음과 같은 형식으로 주어진다.
는 격자의 크기이고, 는 번 하늘다람쥐의 시작점이다.
12출력한 배치는 모든 조건을 만족해야 한다. 가능한 답이 여러 가지라면 아무거나 출력해도 된다.
| 3 | 60 | 추가적인 제약이 없다. |