The genetic code of an abstract primitivus (Primitivus cycle) is a sequence of natural numbers $K = (A_1, \dots, A_n)$. We define a feature of a primitivus as a pair of numbers $(l, r)$ that appear consecutively in the genetic code, meaning there exists an $i$ such that $l = A_i$ and $r = A_{i+1}$. There are no $(p, p)$ features in the genetic code of a primitivus.

Task

Write a program that: 1. Reads the list of features. 2. Calculates the length of the shortest genetic code containing all given features. 3. Writes the result to the output.

Input

The first line contains a positive integer $n$, which is the number of distinct features of the primitivus. Each of the following $n$ lines contains two space-separated integers $l$ and $r$ ($1 \le l \le 1000, 1 \le r \le 1000$). The pair $(l, r)$ is a feature of the primitivus. Features in the input are not repeated.

Output

Write a single integer on the first line, which is the length of the shortest genetic code for the primitivus.

Examples

Input 1

12
2 3
3 9
9 6
8 5
5 7
7 6
4 5
5 1
1 4
4 2
2 8
8 6

Output 1

15

Note

The following genetic code contains all features from the input: $(8, 5, 1, 4, 2, 3, 9, 6, 4, 5, 7, 6, 2, 8, 6)$