OI题库

问题描述

一个 primitivus 的 遗传密码 是一串自然数 K= ( a_1,...,a_n ) 。所有在 primitivus 的遗传密码中连续出现的数对 ( l , r ) 被称为一个 primitivus 的 特征 。例如存在一个 i ， l=a[i], r=a[i+1] 。在 primitivus 的遗传密码中没有形如 ( p , p ) 的特征。 任务

写一个程序

• 从输入文件中读入特征的列表
• 计算 primitivus 的遗传密码的最短长度
• 将结果写到输出文件

输入格式

在输入文件的第一行有一个正整数 n ，表示 primitivus 的遗传密码的不同的特征。在接下来的 n 行中，每行有一对自然数 l 和 r ，用空格隔开， 1 <= l <= 1000, 1 <= r <= 1000 。数对 ( l , r ) 是 primitivus 的特征。特征不会在输入文件中重复出现。

输出格式

你的程序应当向输出文件输出一个数，表示包含输入文件中所有特征的最短的 primitivus 遗传密码的长度。

输入样例

12
2 3
3 9
9 6
8 5
5 7
7 6
4 5
5 1
1 4
4 2
2 8
8 6 

输出样例

15

注释

下面的遗传密码包含了所有特征：

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