미르코는 N²-[N/2] (단, [x]는 x의 정수부분) 개의 도미노를 가지고 도미노 밟기 놀이를 하려고 한다. 

먼저, N행에 도미노를 나열하는데, 짝수 행에 N-1개의 도미노를 일렬로 배열하고, 홀수 행에는 N개의 도미노를 일렬로 배열한다. 

N=5인 경우 다음과 같은 형태로 도미노를 배열하게 된다.

 

 

 

 

미르코는 각 도미노에 1~N²-[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~N²-[N/2]개의 줄에는 각 도미노에 써져 있는 6 이하의 두 자연수(왼쪽 수가 먼저 입력됨)가 주어진다.

첫 번째 줄에는 도달할 수 있는 가장 큰 도미노로 가기 위해 밟아야 하는 최소 도미노 수를 출력한다. 두 번째 줄에는 그 때 밟는 도미노의 번호를 출력한다. 답이 여러 개이면 그 중 하나만 출력한다.

5
1 4
4 5
3 4
5 4
5 2
4 2
5 6
4 4
6 5
2 4
5 1
6 1
1 6
2 3
4 2
5 3
1 2
5 5
4 1
2 2
4 3
2 3
3 4

7
1 2 7 12 17 22 23

3
1 2
2 3
6 6
2 4
3 5
6 6
4 5
5 6

4
1 2 5 8

4
1 5
5 3
5 5
5 6
5 3
6 4
4 5
2 5
2 4
4 3
2 4
5 2
1 4
1 6

7
1 5 8 12 9 10 13