Mister No (tên thật là Jerry Drake) là một nhân vật truyện tranh thường xuyên gặp nhiều rắc rối nhưng thường có thể thoát ra được. Tuy nhiên, lần này không dễ dàng như vậy. Anh ta đang tìm kiếm kho báu của người Maya cổ đại và trong quá trình đó, anh ta tình cờ tìm thấy một ngôi đền bị mất. Bên trong ngôi đền có một hội trường lớn, bên trong hội trường có một vật tổ bằng đá với những dòng chữ là chìa khóa để hiểu mục đích của cuộc sống (42). Tuy nhiên, để đến được Vật tổ là một thử thách lớn.

Vật tổ nằm ở phía đối diện của sảnh từ lối vào. Sàn của hội trường được lát bằng gạch đá có nét giống gạch domino một cách nổi bật. Mỗi ô được chia thành hai nửa (hình vuông) và mỗi nửa có số từ một đến sáu, bao gồm, được đục vào đó. Các ô được sắp xếp thành ~N~ hàng, với ~N~ ô ở mỗi hàng số lẻ và ~N – 1~ ô ở mỗi hàng đánh số chẵn. Hình ảnh bên dưới tương ứng với ví dụ thử nghiệm đầu tiên ~(N=5)~:

Chỉ có thể bước từ ô này sang ô liền kề nếu hai ô có số giống nhau trên các nửa có chung một cạnh. Giúp Mister No tìm ra con đường ngắn nhất đến Vật tổ bằng cách xác định chuỗi các ô (xuất ra chuỗi nhãn của các ô, được mô tả bên dưới) cần được bước lên, theo thứ tự, từ ô đầu tiên đến ô cuối cùng trên đường đi. Nếu không có đường dẫn đến Vật tổ, hãy tìm đường đi ngắn nhất đến ô có nhãn lớn nhất (để Mister No có thể thực hiện một cú nhảy anh hùng). Các viên gạch đá được dán nhãn theo thứ tự hàng lớn: ở hàng đầu tiên, viên gạch đầu tiên có nhãn ~1~, viên cuối cùng là ~N~; ở hàng thứ hai, ô đầu tiên là ~N + 1~ và ô cuối cùng là ~2*N – 1~, v.v. Lối vào dẫn đến ô có nhãn ~1~ và vật tổ nằm ở ô cuối cùng ở hàng cuối cùng. Mister No luôn bắt đầu từ lối vào.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(1 \le N \le 500)~, số hàng gạch đá. Mỗi dòng trong số ~N*N - N/2~ dòng sau (trong đó “/” là viết tắt của phép chia số nguyên) chứa hai số nguyên dương ~A_i~ và ~B_i~ ~(1 ≤ Ai, Bi 6, 1 ≤ i ≤ N * N - N/2)~ , các giá trị được đục tương ứng ở nửa bên trái và bên phải của ô ~i~.

Output

• Dòng đầu ra đầu tiên phải chứa độ dài (tính bằng ô) của đường đi ngắn nhất được yêu cầu.
• Dòng đầu ra thứ hai phải chứa dãy số nguyên dương cách nhau bằng dấu cách, nhãn các ô trên đường đi ngắn nhất. Vì có thể tồn tại nhiều đường đi ngắn nhất, hãy xuất ra bất kỳ đường đi nào trong số đó.

Scoring

• Nếu chỉ có dòng đầu ra đúng thì lời giải được thưởng 50% số điểm cho câu test đó.

Sample Input 1

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

Sample Output 1

7
1 2 7 12 17 22 23

Sample Input 2

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

Sample Output 2

4
1 2 5 8

Sample Input 3

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

Sample Output 3

7
1 5 8 12 9 10 13