#P2451. [SDOI2005] 遗传代码

[SDOI2005] 遗传代码

题目描述

抽象的 primitivus(Primitivus 循环)的遗传代码是一系列自然数 K=(A1,A2,,An)K=(A_1,A_2,\cdots,A_n)。我们所说的 primitivus 的特征是一个数对 (l,r)(l,r),表示 l,rl,rAA连续出现。即存在一个 ii,使得 Ai=lA_i=lAi+1=rA_{i+1}=r。在 primitivus 的遗传代码中没有 (p,p)(p,p) 特征。

任务

写一个程序:

  1. 从文本文件读特征列表;
  2. 计算所给特征的最短遗传代码长度;
  3. 输出答案。

输入格式

第一行有一个正整数 nn,它是 primitivus 的不同特征的数量。

接下来 nn 行,每一行中有两个被空格号隔开的数字 llrr。数字对 (l,r)(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)(8, 5, 1, 4, 2, 3, 9, 6, 4, 5, 7, 6, 2, 8, 6)

数据范围及约定

对于全部数据,满足 0l10000 \le l \le 10000r10000 \le r \le 1000