1534：原始生物

题目描述

原始生物的遗传密码是一个自然数的序列 $K = (a_1, \cdots, a_n)$。原始生物的特征是指在遗传密码中连续出现的数对 $(l, r)$，即存在自然数 $i$ 使得 $l = a_i$ 且 $r = a_{i+1}$。在原始生物的遗传密码中不存在 $(p, p)$ 形式的特征。

求解任务，请设计一个程序：

• 读入一系列的特征。
• 计算包含这些特征的最短的遗传密码。
• 将结果输出。

输入格式

第一行是一个整数 $n$，表示特征的总数。在接下来的 $n$ 行里，每行都是一对由空格分隔的自然数 $l$ 和 $r$。数对 $(l, r)$ 是原始生物的特征之一。输入文件中的特征不会有重复。

输出格式

唯一一行应该包含一个整数，等于包含了输入文件中所有特征的遗传密码的最小长度。

样例

样例输入 #1

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

样例输出 #1

15

样例解释 #1

• $n=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)
• 目标：构造一个最短的序列，使得每个特征都作为连续两个元素出现在序列中（可以重复使用元素，但不能有 $(p,p)$ 这样的特征，即序列中相邻两个数不能相同）。
• 一种最短序列为：$(8,5,1,4,2,3,9,6,4,5,7,6,2,8,6)$，长度为 $15$。
• 验证：从该序列可以提取出所有特征（注意序列中相邻数对）：
  • 位置 1-2: (8,5)
  • 2-3: (5,1)
  • 3-4: (1,4)
  • 4-5: (4,2)
  • 5-6: (2,3)
  • 6-7: (3,9)
  • 7-8: (9,6)
  • 8-9: (6,4)
  • 9-10: (4,5)
  • 10-11: (5,7)
  • 11-12: (7,6)
  • 12-13: (6,2)
  • 13-14: (2,8)
  • 14-15: (8,6)
• 包含了所有 $12$ 个特征，且长度为 $15$。

数据范围

• $1 \le l, r \le 1000$

时空限制

• 时间限制：3000 ms
• 内存限制：131072 KB

注意：本题可以转化为有向图欧拉路径问题。将每个不同的自然数看作顶点，每个特征 $(l, r)$ 看作一条从 $l$ 指向 $r$ 的有向边。题目要求构造一个最短的序列，使得每条边恰好出现一次（因为特征不重复），且序列中相邻元素不能相同（即不存在自环，题目已保证没有 $(p,p)$ 特征）。这恰好是求有向图的欧拉路径（或回路）的长度。序列长度等于边数 + 1（因为 $n$ 条边对应 $n+1$ 个顶点）。但图可能不连通或有多个连通分量，此时需要添加一些额外的边（即重复使用某些顶点）来连接各个连通分量，从而使得整个序列包含所有特征。实际上，我们需要找到一条路径，覆盖所有边，且允许重复经过顶点（但边不能重复）。这就是求欧拉路径，如果图存在欧拉路径，则最短长度就是 $n+1$；如果图不连通，则需要添加一些额外的边（即重复某些顶点）来连接各个连通分量，此时长度会增加。

具体算法：

1. 统计每个顶点的入度和出度。
2. 用并查集维护连通性（注意是有向图，但连通性按无向考虑，即弱连通）。
3. 对于每个连通分量，计算其奇度顶点（入度 ≠ 出度）的情况。如果该分量存在欧拉回路（所有顶点入度=出度），则该分量需要单独一个回路；如果存在欧拉路径（恰好两个顶点入度≠出度，且一个入度-出度=1，另一个出度-入度=1），则也可以一笔画。
4. 整个图可能需要连接各个连通分量，形成一条路径覆盖所有边。这需要添加一些额外的边（即重复某些顶点），使得整个图变成弱连通且存在欧拉路径。
5. 最小长度 = 总边数 + 需要添加的边数（即连通分量数 - 1 + 调整奇度顶点所需的额外边数？）。实际上，答案 = n + max(0, 连通分量数 - 1) + sum(max(0, (入度-出度)的绝对值/2))？需要推导。

本题是求最短的序列长度，即包含所有特征的最短序列。由于特征不会有重复，每条边必须恰好出现一次，所以问题等价于求有向图的最小欧拉路径覆盖（允许重复顶点）。最终答案是 n + 需要添加的边数。