Minimum Length of Primitivus Genetic Code

Consider an abstract genetic code of primitivus represented by a sequence of natural numbers (K=(A_1,A_2,\cdots,A_n)). A characteristic of primitivus is a pair ((l,r)) which appears consecutively in (K); that is, there exists an index (i) such that (A_i=l) and (A_{i+1}=r). Note that no characteristic of the form ((p,p)) appears in the genetic code.

Given a list of features (pairs) read from a text file, your task is to compute the minimum possible length of a genetic code sequence that contains every given feature as a contiguous sub‐sequence. In other words, you are given a collection of 2-digit "words" (with distinct digits) and you are allowed to insert extra digits (transitions between different numbers only) if necessary so that all these words appear as substrings. The answer is the length (number of digits) of the shortest such sequence.

Hint: For a connected group of features, if (E) is the number of required edges (features) and for every vertex (v), let (d(v)=\text{outdeg}(v)-\text{indeg}(v)). If the component has an Eulerian trail (i.e. (\sum_{v\in comp}\max(0,d(v))=0)), then the minimal sequence for that component is of length (E+1); otherwise, it is (E+\sum_{v\in comp}\max(0,d(v))). When features belong to different connected components (when viewed as an undirected graph), their minimal sequences cannot overlap. Thus, the overall answer is the sum over all components.

inputFormat

The first line contains a single integer (n) representing the number of features. Each of the following (n) lines contains two distinct natural numbers (l) and (r) separated by spaces, representing a feature ((l,r)).

outputFormat

Output a single integer indicating the minimum length of the genetic code sequence that contains all the given features as contiguous pairs.

sample

1
1 2

2