P5921 [POI 1999 R3] Primitive Organisms

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

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.

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 a single integer in one line, representing the length of the shortest genetic code that contains these features.

### 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