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

Totem nằm ở phía đối diện của hội trường từ lối vào. Sàn của phòng được lát bằng gạch. Mỗi gạch được chia thành hai nửa (hình vuông), và mỗi một nửa là một số từ 1 đến 6. Gạch được sắp xếp thành ~N~ hàng, với ~N~ viên gạch trong mỗi hàng lẻ và ~N - 1~ viên gạch trong mỗi hàng chẵn.

Chỉ có thể bước từ một gạch đến một gạch liền kề nếu hai gạch có số bằng với số trên một nửa của nó. Giúp Mister No tìm ra con đường ngắn nhất để đến Totem bằng cách xác định trình tự của gạch cần được bước vào, theo thứ tự, từ đầu cho tới cuối trên con đường. Nếu không có con đường tốt để đến Totem, tìm đường đi ngắn nhất đến gạch có nhãn lớn nhất. Gạch được dán nhãn như sau: trong hàng đầu tiên, gạch đầu tiên được ghi trên nhãn 1, và cuối cùng là ~N~; ở hàng thứ hai, gạch đầu tiên là ~N + 1~, và cuối cùng ~2 \times N - 1~, và ... Các lối vào là gạch với nhãn 1, và là totem trên gạch cuối cùng ở hàng cuối cùng. Mister luôn luôn bắt đầu từ lối vào.

Yêu cầu: Tìm độ dài của con đường ngắn nhất cần tìm.

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 \times N - N / 2~ dòng sau chứa hai số nguyên ~A_i~ và ~B_i~ (~1 \le A_i, B_i \le 6~, ~1 \le i \le N \times N - N / 2~), các giá trị vào bên trái và bên phải của gạch tương ứng.

Output

• Độ dài của con đường ngắn nhất cần tìm.

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