문제
미르코는 N2-[N/2] (단, [x]는 x의 정수부분) 개의 도미노를 가지고 도미노 밟기 놀이를 하려고 한다.
먼저, N행에 도미노를 나열하는데, 짝수 행에 N-1개의 도미노를 일렬로 배열하고, 홀수 행에는 N개의 도미노를 일렬로 배열한다.
N=5인 경우 다음과 같은 형태로 도미노를 배열하게 된다.
미르코는 각 도미노에 1~N2-[N/2] 의 번호를 행이 작은 순서대로 왼쪽에서부터 오른쪽 방향으로 붙이게 된다.
위 그림에서는 7번 도미노는 2행에 있는 (5,6)이 쓰여 있는 도미노이고, 15번 도미노는 4행에 있는 (4,2)가 쓰여 있는 도미노와 같다.
미르코는 1번 도미노에서부터 시작해 여러 도미노들을 밟고 간다.
미르코가 한 도미노를 밟았을 때, 그 도미노와 한 모서리를 공유하면서 그 모서리 양 끝의 두 수가 같은 도미노만 밟을 수 있다.
1번 도미노와 2번 도미노는 한 모서리를 공유하면서 그 모서리 양 끝의 두 수가 4로 같기 때문에 1번 도미노를 밟고 연달아 2번 도미노를 밟을 수 있다.
반면 2번 도미노와 3번 도미노는 한 모서리를 공유하지만
그 모서리 양 끝의 두 수가 5, 3으로 다르기 때문에 2번 도미노를 밟고 연달아 3번 도미노를 밟을 수 없다.
도미노 밟기 놀이의 목적은 보다 빨리 번호가 큰 도미노를 밟는 것이다.
미르코를 도와 도달할 수 있는 가장 큰 도미노로 가기 위해 밟아야 하는 최소 도미노 수와 그 때의 도미노 번호를 구하는 프로그램을 작성하여라.
입력
첫 번째 줄에는 도미노 놀이 게임판의 크기 N이 주어진다. (1 ≤ N ≤ 500) 두 번째 줄부터 1~N2-[N/2]개의 줄에는 각 도미노에 써져 있는 6 이하의 두 자연수(왼쪽 수가 먼저 입력됨)가 주어진다.
출력
예제1
5
14
45
34
54
52
42
56
44
65
24
51
61
16
23
42
53
12
55
41
22
43
23
34
7
12712172223
예제2
3
12
23
66
24
35
66
45
56
4
1258
예제3
4
15
53
55
56
53
64
45
25
24
43
24
52
14
16
7
1581291013
출처
2013.03.09 모의테스트3