#P2451. [SDOI2005] 遗传代码
[SDOI2005] 遗传代码
题目描述
抽象的 primitivus(Primitivus 循环)的遗传代码是一系列自然数 。我们所说的 primitivus 的特征是一个数对 ,表示 在 中连续出现。即存在一个 ,使得 ,。在 primitivus 的遗传代码中没有 特征。
任务
写一个程序:
- 从文本文件读特征列表;
- 计算所给特征的最短遗传代码长度;
- 输出答案。
输入格式
第一行有一个正整数 ,它是 primitivus 的不同特征的数量。
接下来 行,每一行中有两个被空格号隔开的数字 和 。数字对 是 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
提示
样例解释
以下是一种符合题意的最短的遗传代码。它符合输入数据中给出的所有的特征:
数据范围及约定
对于全部数据,满足 ,。