Primitivus

Time limit3sMemory limit128 MB

Summary

Given a set of ordered pairs, find the shortest sequence in which every pair appears consecutively at least once.

Level: Medium7 of 10
Topics: Graph, Shortest path, Dynamic programming, Bit manipulation
Solved: No attempts yet

Problem

The genetic code of the abstract organism Primitivus recurencis is a sequence of natural numbers $K = (a_1, a_2, \dots, a_n)$ . A feature of a primitivus is any ordered pair $(l, r)$ that appears consecutively in the genetic code, that is, there exists an index $i$ such that $a_i = l$ and $a_{i+1} = r$ . A genetic code never contains a feature of the form $(p, p)$ : no value is ever immediately followed by itself.

You are given a set of features. Write a program that:

reads the list of features from standard input,
computes the length of the shortest genetic code that contains all of the given features,
writes that length to standard output.

Input

The first line contains one positive integer $n$ , the number of distinct features. Each of the next $n$ lines contains two natural numbers $l$ and $r$ separated by a single space ( $1 \le l \le 1000$ , $1 \le r \le 1000$ , $l \ne r$ ), describing one feature $(l, r)$ . No feature appears more than once.

Output

Print a single integer: the length of the shortest genetic code that contains every feature from the input.

Hint

For the example input, all features appear in this genetic code of length 15:

$(8, 5, 1, 4, 2, 3, 9, 6, 4, 5, 7, 6, 2, 8, 6)$ .

Examples4

Example 1

Input

Expected output

Example 2
Input
```
1
1 2
```
Expected output
```
2
```
Example 3
Input
```
2
1 2
2 1
```
Expected output
```
3
```
Example 4
Input
```
3
1 2
2 3
3 1
```
Expected output
```
4
```