你好！我是你的OI金牌教练。

在上一道关于“战国七雄”的题目中，我们通过图的遍历（BFS/DFS）解决了一个静态图的连通块计数问题。

今天，我们将时间轴推移至秦朝，见证中国历史上第一次大一统。我们将结合**“书同文，车同轨，统一度量衡”的历史背景，学习一种专门用于处理不相交集合的合并与查询**的高级数据结构——并查集 (Disjoint Set Union, DSU)。

这道题是 GESP 6级 的核心考点，它与之前的图遍历算法有明显的递进关系：BFS/DFS 适合处理静态图的连通性，而并查集更擅长处理动态添加边过程中的连通性维护，且代码更短、效率更高。

---

第一部分：背景知识讲解

1. 秦始皇统一六国 (Unification by Qin Shi Huang)

公元前221年，秦王嬴政灭掉六国，建立了中国历史上第一个统一的中央集权的封建国家——秦朝。

2. 统一度量衡与货币 (Standardization)

在统一之前，各国的货币形状、重量各异（如赵国的铲币、齐国的刀币、楚国的蚁鼻钱），度量衡标准也不同，这极大地阻碍了经济交流。 秦始皇下令废除六国货币，以秦国的**圆形方孔钱（半两钱）**为标准货币，并统一了度量衡和文字（小篆）。

3. 算法递进：从遍历到集合管理

在“战国”那一题中，我们是在一切尘埃落定后（图建好了），去数有多少个圈子。 但在秦朝统一的过程中，是一个动态的过程：今天把赵国货币废除并入秦制，明天把燕国度量衡改为秦制。我们需要一种数据结构，能够快速支持两个操作：

1. 合并 (Union)：宣布两个原本不通用的系统现在通用了。
2. 查询 (Find)：判断两个地方是否已经使用了相同的标准。

这就是并查集的用武之地。相比于 $O(N+M)$ 的 BFS，并查集在路径压缩优化下，单次操作的时间复杂度近乎 $O(1)$（实际上是反阿克曼函数 $O(\alpha(N))$），效率极高。

---

第二部分：题目内容

题目名称：大秦的统一 (The Unification of Great Qin)

题目描述

秦始皇刚刚统一了六国，面对的是 $N$ 个刚刚归附的郡县，编号为 $1$ 到 $N$。 起初，这 $N$ 个郡县各自保留着原有的度量衡和货币标准，互不通用。也就是说，初始状态下有 $N$ 个独立的经济区。

为了推进统一大业，秦始皇连续颁布了 $M$ 道圣旨。 第 $i$ 道圣旨的内容是：强制令郡县 $u_i$ 和郡县 $v_i$ 实行相同的度量衡标准。 注意：标准具有传递性。如果 A 和 B 通用，B 和 C 通用，那么 A 和 C 也视为通用，它们同属于一个经济区。

李斯作为丞相，需要向秦始皇汇报统一工作的进度。请你编写程序，根据这 $M$ 道圣旨，计算出：

1. 在颁布完所有圣旨后，全国还剩下多少个独立的经济区？（最终目标是 1 个）。
2. 目前最大的一个经济区包含了多少个郡县？
3. 在推行过程中，有多少道圣旨是**“多余”**的？（注：如果颁布圣旨时，$u$ 和 $v$ 实际上已经通过其他路径连通了，这道圣旨就是多余的）。

输入格式

第一行包含两个正整数 $N, M$。

• $N$ 表示郡县的数量。
• $M$ 表示颁布圣旨的数量。

接下来 $M$ 行，每行包含两个正整数 $u, v$，表示一道圣旨要求 $u$ 和 $v$ 统一标准。

输出格式

输出一行，包含三个整数，中间用空格隔开，依次表示：

1. 最终剩下的独立经济区数量。
2. 最大的经济区包含的郡县数。
3. 多余的圣旨数量。

输入输出样例 #1

输入：

5 4
1 2
2 3
4 5
1 3

输出：

2 3 1

样例 #1 解释： 初始：{1}, {2}, {3}, {4}, {5}，共 5 个区。

1. 1 2：1, 2 合并。现状：{1, 2}, {3}, {4}, {5}。
2. 2 3：2, 3 合并。由于 1-2 已通，故 {1, 2, 3} 成为一个区。现状：{1, 2, 3}, {4}, {5}。
3. 4 5：4, 5 合并。现状：{1, 2, 3}, {4, 5}。
4. 1 3：要求 1, 3 合并。但在第 2 步后，1 和 3 已经在同一个区了，所以这是一道多余的圣旨。

最终结果：

• 独立区数量：2 个 ({1,2,3} 和 {4,5})。
• 最大区大小：3 (即 {1,2,3})。
• 多余圣旨数：1。

输入输出样例 #2

输入：

6 5
1 2
3 4
5 6
1 3
3 5

输出：

1 6 0

样例 #2 解释： 经过 5 次合并，所有郡县最终都连在了一起，形成了 1 个大一统的经济区，大小为 6。 没有多余的圣旨，每一步都连接了原本不通的区域。

数据范围

对于 $100\%$ 的数据：

• $1 \le N \le 10^5$
• $1 \le M \le 2 \times 10^5$
• $1 \le u, v \le N$

---