Tutor Man

Tutor Man has arrived at an ancient Mayan temple to recover his stolen tutoring notes. The notes lie on the far side of the temple entrance, but a deep cliff separates the two sides. Just then, giant domino tiles fall from the sky and form a bridge across the cliff.

Each domino tile is divided into two square pieces, and each piece bears a number between $1$ and $6$ inclusive.

The tiles are laid out in $N$ rows. An odd-numbered row holds $N$ tiles and an even-numbered row holds $N-1$ tiles, with the even rows offset by half a tile. The figure below shows the layout when $N=5$.

To step from one tile to another, the two tiles must be adjacent, and the two pieces that share the touching edge must hold the same number.

Tiles are numbered in row-major order. In the first row the first tile is number $1$ and the last is number $N$. In the second row the first tile is number $N+1$ and the last is number $2N-1$.

Tutor Man may start only from the first tile of the first row (tile $1$), and the notes rest on the last tile of the last row. Find the path from the first tile to the last tile of the last row that passes through the fewest tiles.

If the last tile of the last row cannot be reached, the destination becomes the tile with the largest number among all tiles reachable from the first tile.

The first line contains $N$. ($1 \le N \le 500$)

Each of the next $N^2 - \lfloor N/2 \rfloor$ lines contains the two numbers $A_i$ and $B_i$ of one tile. ($1 \le A_i, B_i \le 6$) $A_i$ is the number on the left piece of tile $i$ and $B_i$ is the number on the right piece. Tiles are given in increasing order of their number.

On the first line, print the length of the shortest path (the number of tiles it passes through).

On the second line, print the numbers of the tiles on that path in order, separated by spaces. If several shortest paths exist, print the lexicographically smallest one, comparing the sequences of tile numbers position by position.