Primitivus

시간 제한3초메모리 제한128 MB

요약

순서쌍 집합이 주어질 때, 모든 순서쌍이 연속으로 한 번 이상 나타나는 가장 짧은 수열의 길이를 구한다.

난이도: 보통10점 중 7점
유형: 그래프, 최단 경로, 동적 계획법, 비트 연산
정답자: 아직 제출이 없습니다

문제

추상적인 생물 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)$ .

예제4

예제 1

입력

예상 출력

예제 2
입력
```
1
1 2
```
예상 출력
```
2
```
예제 3
입력
```
2
1 2
2 1
```
예상 출력
```
3
```
예제 4
입력
```
3
1 2
2 3
3 1
```
예상 출력
```
4
```