시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB82122623223733.558%

문제

나이트 투어는 체스판에서 나이트가 모든 칸을 정확히 한 번씩 방문하며, 마지막으로 방문하는 칸에서 시작점으로 돌아올 수 있는 경로이다. 다음 그림은 나이트 투어의 한 예이다.

영식이는 6×6 체스판 위에서 또 다른 나이트 투어의 경로를 찾으려고 한다. 체스판의 한 칸은 A, B, C, D, E, F 중에서 하나와 1, 2, 3, 4, 5, 6 중에서 하나를 이어 붙인 것으로 나타낼 수 있다. 영식이의 나이트 투어 경로가 주어질 때, 이것이 올바른 것이면 Valid, 올바르지 않으면 Invalid를 출력하는 프로그램을 작성하시오.

입력

36개의 줄에 나이트가 방문한 순서대로 입력이 주어진다. 체스판에 존재하는 칸만 입력으로 주어진다.

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력 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

예제 출력 1

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

예제 출력 2

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

예제 출력 3

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

예제 출력 4

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

예제 출력 5

Invalid

출처