XLII 保加利亚国家信息学奥林匹克竞赛

市级赛，2025 年 12 月 20 日 A 组（11–12 年级）

---

题目 A1：贝洛特（BELOT）

时间限制： 1.5 秒 内存限制： 1024 MB

---

题目背景

尼古拉和他的朋友们不久前聚在一起参加了一次奥林匹克集训。同时，大家主要在讨论：​谁是玩贝洛特（Belot）这款游戏最厉害的人​。尼古拉声称自己是最强的，但其他人对此表示怀疑。

一共有 (N) 个朋友，我们用数字 1 到 (N) 来表示他们。 他们决定在接下来的 (N) 天里进行 (M) 场贝洛特对局，每一场对局​恰好由两个人参加​​。 我们用一个有序对 ((x_i, y_i)) 来表示一场比赛，其中 (1 \le x_i < y_i \le N)。

在第 (a) 天（(1 \le a \le N)），朋友 (a) 会进行所有包含他本人的尚未进行的比赛（比赛不会重复进行）。

事实证明，可能需要安排​额外的比赛​。更具体地说：

如果在第 (a) 天，朋友 (a) 参加了比赛 ((a, b))（(a < b)）以及比赛 ((a, c))（(a < c)，且 (c \ne b)）， 那么在​之后的某一天​，必须安排一场由朋友 (b) 和 (c) 参加的比赛，以便他们也能彼此比较实力。

注意：

• 比赛 ((a, b)) 和 ((a, c)) 不一定来自最初给定的比赛列表，它们也可能是后来新增的比赛。
• 这可能会使比赛总数变得很大，因此请你编写程序 ​belote​，计算​最终总共需要进行多少场比赛​。

---

输入格式

标准输入第一行包含两个整数 (N) 和 (M) —— 朋友人数与​最初计划的比赛数量​。

接下来的 (M) 行中，每行包含两个整数 ​**(x_i, y_i)​，表示朋友 (x_i) 与 (y_i) 之间有一场比赛（(x_i < y_i)）。 保证​不会有重复的比赛**​。

---

输出格式

输出​一个整数​：表示​最终需要进行的比赛总数​（包括最初的和后来新增的）。

---

数据范围

• (1 \le N, M \le 100,000)

---

子任务

子任务	分值	需要通过的前置子任务	(N) 上限	其他限制
0		—		仅样例
1	20	0	≤ 100	—
2	30	0–1	≤ 3500
3	5	0–2	≤ 5000
4	10	0–3	≤ 50000
5	15	—	≤ 100000	对每个 (1 \le k \le N)，最多只有一场初始比赛 ((x_i, y_i)) 满足 (y_i = k)
6	20	0–5		—

说明：

• 每个子任务的分数，只有在通过该子任务以及它所依赖的所有子任务后才能获得。
• 你可以认为这里玩的贝洛特是​两人对战版​，而不是常见的四人版本。

---

样例

输入：

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

输出：

15

样例说明： 每天的比赛安排如下（同一天内的顺序无关紧要）：

• ​第 1 天​： (1,2), (1,3) → 这会触发一场额外比赛： (2,3)
• ​第 2 天​： (2,3), (2,5), (2,6), (2,7) → 这会触发额外比赛： (3,5), (3,6), (3,7), (5,6), (5,7), (6,7)
• ​第 3 天​： (3,5), (3,6), (3,7) → 不会产生新的额外比赛（注意：不会重复 (3,1) 和 (3,2)）
• ​第 4 天​： (4,7), (4,8) → 没有新的额外比赛
• ​第 5 天​： (5,6), (5,7) → 没有新的额外比赛
• ​第 6 天​： (6,7)
• ​第 7 天​： (7,8)
• ​第 8 天​： 朋友 8 没有剩余比赛
• ​第 9 天​： 朋友 9 没有比赛

最终新增的比赛有： (2,3), (3,5), (3,6), (3,7), (5,6), (5,7), (6,7)

注意： 虽然存在 (6,7) 和 (7,8) 两场比赛，但不会触发 (6,8)，因为前者在第 6 天进行，后者在第 7 天进行，并不发生在同一天同一个“中心人物”的比赛集中。

---