시간 제한2초메모리 제한128 MB
6x6 체스판에서 주어진 36개 칸의 방문 순서가 유효한 나이트의 순회(연속 이동과 마지막에서 처음으로의 복귀 포함)인지 판별합니다.
나이트 투어는 체스판에서 나이트가 모든 칸을 정확히 한 번씩 방문하고, 마지막으로 방문한 칸에서 다시 시작 칸으로 나이트처럼 이동할 수 있는 경로이다.
6×6 체스판의 각 칸은 A부터 F까지의 문자 하나와 1부터 6까지의 숫자 하나를 붙여 나타낸다. 나이트가 방문한 36개의 칸이 순서대로 주어질 때, 이 경로가 올바른 나이트 투어인지 판정하시오.
36개의 줄에 걸쳐 나이트가 방문한 칸이 순서대로 주어진다. 입력으로 주어지는 칸은 모두 6×6 체스판 위에 존재한다.
경로가 올바른 나이트 투어이면 Valid, 아니면 Invalid를 출력한다.
예제 1
A1 B3 A5 C6 E5 F3 D2 F1 E3 F5 D4 B5 A3 B1 C3 A2 C1 E2 F4 E6 C5 A6 B4 D5 F6 E4 D6 C4 B6 A4 B2 D1 F2 D3 E1 C2
Valid
예제 2
A1 C2 E3 F5 D4 B3 A1 C2 E3 F5 D4 B3 A1 C2 E3 F5 D4 B3 A1 C2 E3 F5 D4 B3 A1 C2 E3 F5 D4 B3 A1 C2 E3 F5 D4 B3
Invalid
예제 3
D4 F5 D6 B5 A3 B1 D2 F1 E3 D1 F2 E4 F6 D5 B6 A4 B2 C4 A5 C6 E5 F3 E1 C2 A1 B3 C5 E6 F4 E2 C3 A2 C1 D3 B4 A6
Invalid
예제 4
D4 F5 D6 B5 A3 B1 D2 F1 E3 D1 F2 E4 F6 D5 B6 A4 B2 C4 A5 C6 E5 F3 E1 C2 A1 B3 C5 A6 B4 A2 C3 E2 C1 D3 F4 E6
Valid
예제 5
C5 D3 F2 D1 B2 A4 B6 D5 C3 E4 F6 B3 A1 C2 E1 F3 E5 C6 A5 C4 A3 B1 D2 F1 E3 F5 D6 B5 D4 E6 F4 E2 C1 A2 B4 A6
Invalid