Background

Thanks to @Jiangly for pointing out an error, and to @NaCly_Fish for modifying the testdata.

Problem Description

The genetic code of a primitive organism is a sequence of natural numbers $K=\{a_1,\dots,a_n\}$.

A feature of a primitive organism refers to a pair of numbers $(l,r)$ that appears consecutively in the genetic code $K$, that is, there exists a natural number $i$ such that $l=a_i$ and $r=a_{i+1}$. It is guaranteed that there is no feature of the form $(p,p)$.

Task

Design a program to:

• read a list of features;
• compute the length of the shortest genetic code that contains these features;
• output the result.

Input Format

The first line contains an integer $n$, representing the total number of features.

In the next $n$ lines, each line contains a pair of natural numbers $l$ and $r$ separated by a space, meaning that the pair $(l,r)$ is one of the features of the primitive organism.

The features in the input file may contain duplicates; please remove duplicates.

Output Format

Output a single integer in one line, representing the length of the shortest genetic code that contains these features.

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

$\{8,5,1,4,2,3,9,6,4,5,7,6,2,8,6\}$ is a genetic code that satisfies the requirement.

Constraints

For $100\%$ of the data, $1\le n\le 10^6$, $1\le l,r\le 1000$.

Translated by ChatGPT 5