Description

Original Source: POI 1999

The genetic code of a primitive organism is a sequence of natural numbers $K=(a_1,\cdots,a_n)$. A characteristic of the primitive organism is a pair of numbers $(l,r)$ that appears consecutively in the genetic code, i.e., there exists a natural number $i$ such that $l=a_i$ and $r=a_{i+1}$. In the genetic code of the primitive organism, there are no characteristics of the form $(p,p)$.

Your task is to design a program that:

• Reads a series of characteristics.

• Computes the shortest genetic code that contains all these characteristics.

• Outputs the result.

Input Format

The first line contains an integer $n$, representing the total number of characteristics. Each of the next $n$ lines contains a pair of natural numbers $l$ and $r$ separated by a space. Each pair $(l,r)$ is one of the characteristics of the primitive organism. There are no duplicate characteristics in the input file.

Output Format

The output should consist of a single line containing an integer, which is the minimum length of the genetic code that includes all the characteristics from the input file.

Sample 1

All characteristics from the input file are included in the following genetic code:

$(8, 5, 1, 4, 2, 3, 9, 6, 4, 5, 7, 6, 2, 8, 6)$

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

15

Data Range and Hint

$1 \le l,r \le 1000$