P2451 [SDOI2005] Genetic Code

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.

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 a single line containing one integer, which is the length of the shortest genetic code of the primitivus.

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