Primitivus

추상적인 생물 Primitivus recurencis의 유전 코드는 자연수의 수열 $K = (a_1, a_2, \dots, a_n)$이다. 유전 코드에서 연속으로 이웃하여 나타나는 순서쌍 $(l, r)$, 즉 $a_i = l$이고 $a_{i+1} = r$인 위치 $i$가 존재하는 순서쌍을 프리미티부스의 특징(feature)이라고 한다. 유전 코드에는 $(p, p)$ 형태의 특징이 존재하지 않는다. 즉, 어떤 값도 자기 자신 바로 뒤에 다시 오지 않는다.

특징들의 집합이 주어진다. 다음을 수행하는 프로그램을 작성하시오.

• 표준 입력에서 특징의 목록을 읽는다.
• 주어진 모든 특징을 포함하는 가장 짧은 유전 코드의 길이를 구한다.
• 그 길이를 표준 출력에 출력한다.

첫째 줄에 서로 다른 특징의 개수를 나타내는 양의 정수 $n$이 주어진다. 다음 $n$개의 줄에는 각각 하나의 특징 $(l, r)$을 나타내는 두 자연수 $l$과 $r$이 공백 하나로 구분되어 주어진다 ($1 \le l \le 1000$, $1 \le r \le 1000$, $l \ne r$). 같은 특징은 두 번 이상 주어지지 않는다.

입력으로 주어진 모든 특징을 포함하는 가장 짧은 유전 코드의 길이를 정수 하나로 출력한다.

예제 입력의 모든 특징은 길이가 15인 다음 유전 코드에 모두 나타난다.

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