과외맨

과외맨은 도난당한 과외 노트를 되찾기 위해 고대 마야의 사원에 도착했다. 노트는 사원 입구의 반대편에 놓여 있는데, 그 사이에는 깊은 절벽이 있다. 그때 하늘에서 거대한 도미노 타일들이 떨어지며 절벽을 잇는 다리를 만들었다.

도미노 타일은 두 개의 정사각형 조각으로 나뉘어 있고, 각 조각에는 $1$ 이상 $6$ 이하의 숫자가 적혀 있다.

타일은 $N$개의 줄로 놓여 있다. 홀수 번째 줄에는 $N$개의 타일이, 짝수 번째 줄에는 $N-1$개의 타일이 놓여 있으며, 짝수 번째 줄은 반 칸씩 어긋나게 배치된다. 아래 그림은 $N=5$일 때 타일이 놓인 모습이다.

한 타일에서 다른 타일로 넘어가려면 두 타일이 서로 인접해야 하고, 두 타일이 맞닿은 변을 공유하는 두 조각에 적힌 숫자가 같아야 한다.

타일에는 row-major 순서로 번호가 매겨진다. 첫 번째 줄의 첫 타일은 $1$번, 마지막 타일은 $N$번이다. 두 번째 줄의 첫 타일은 $N+1$번, 마지막 타일은 $2N-1$번이다.

과외맨은 첫 번째 줄의 첫 타일($1$번)에서만 출발할 수 있고, 과외 노트는 마지막 줄의 마지막 타일 위에 놓여 있다. 첫 타일에서 마지막 줄의 마지막 타일까지 이동하는, 지나는 타일의 수가 가장 적은 경로를 찾아야 한다.

만약 마지막 줄의 마지막 타일까지 도달할 수 없다면, 첫 타일에서 도달할 수 있는 타일 중 번호가 가장 큰 타일을 목적지로 삼는다.

첫째 줄에 $N$이 주어진다. ($1 \le N \le 500$)

다음 $N^2 - \lfloor N/2 \rfloor$개의 줄에는 각 타일의 두 숫자 $A_i$와 $B_i$가 주어진다. ($1 \le A_i, B_i \le 6$) $A_i$는 $i$번 타일의 왼쪽 조각에 적힌 숫자, $B_i$는 오른쪽 조각에 적힌 숫자이다. 타일은 번호가 작은 것부터 순서대로 주어진다.

첫째 줄에 가장 짧은 경로의 길이(지나는 타일의 개수)를 출력한다.

둘째 줄에는 그 경로가 지나는 타일의 번호를 순서대로 공백으로 구분하여 출력한다. 가장 짧은 경로가 여러 개라면, 타일 번호의 수열을 앞에서부터 차례로 비교했을 때 사전식으로 가장 작은 경로를 출력한다.