Description

The abstract genetic code of a primitivus (Primitivus loop) is a sequence of natural numbers $K=(A_1,A_2,\cdots,A_n)$. A feature of a primitivus is an ordered pair $(l,r)$, meaning that $l, r$ appear consecutively in $A$. That is, there exists an $i$ such that $A_i=l$, $A_{i+1}=r$. In the genetic code of a primitivus, there is no $(p,p)$ feature.

Task

Write a program to:

1. Read the list of features from a text file.
2. Compute the length of the shortest genetic code that contains all the given features.
3. Output the answer.

Input Format

The first line contains a positive integer $n$, which is the number of distinct features of the primitivus.

Then follow $n$ lines. Each line contains two numbers $l$ and $r$ separated by a space. The pair $(l,r)$ is a feature of the primitivus. In the input file, features do not repeat.

Output Format

Output a single line containing one integer, which is the length of the shortest genetic code of the primitivus.

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

Hint

Sample Explanation

One shortest genetic code that satisfies all the features given in the input is: $(8, 5, 1, 4, 2, 3, 9, 6, 4, 5, 7, 6, 2, 8, 6)$.

Constraints

For all data, $0 \le l \le 1000$, $0 \le r \le 1000$.

Translated by ChatGPT 5