Description

每年在克卢日-纳波卡都会举办一次大型桌游博览会，展示各种新推出的游戏。今年的主要亮点是一款名为 BoardOina 的游戏。

队伍中排有 $n$ 名玩家，等待体验该游戏。玩家按排队顺序编号为 $0$ 到 $n - 1$。编号 $0$ 的玩家在队首，编号 $n - 1$ 的玩家在队尾。

队伍中共有 $m$ 对不同的好友关系。具体而言，对于每个 $i$（$0 \leq i \leq m - 1$），玩家 $x[i]$ 与玩家 $y[i]$ 是好友，且满足 $0 \leq x[i] < y[i] < n$。好友关系是对称的。

考虑从玩家 $s$ 开始的、长度为 $k$ 的连续玩家序列（$0 \leq s < n$ 且 $1 \leq k \leq n - s$）。如果在该序列中，任意两名玩家之间都可以通过该组内的好友关系链相互到达，那么这组玩家构成一个规模为 $k$ 的好友组。具体来说，玩家 $s, s + 1, \ldots, s + k - 1$ 构成规模为 $k$ 的好友组，当且仅当对于任意满足 $s \leq u < v < s + k$ 的玩家 $u$ 和 $v$，存在一列玩家 $p[0], \ldots, p[l - 1]$，使得：

• $l \geq 2$；
• 对于所有 $j \in [0, l - 1]$，都有 $s \leq p[j] < s + k$；
• $p[0] = u$ 且 $p[l - 1] = v$；
• 对于所有 $j \in [0, l - 2]$，玩家 $p[j]$ 与 $p[j + 1]$ 是好友。

特别地，当 $k = 1$ 时，玩家 $s$ 自身就构成一个规模为 $1$ 的好友组。

BoardOina 可供任意人数游玩，但为了让游戏更受欢迎，组织者只允许好友组参与游戏。

同一时间只能有一个组进行游戏。每次从队首玩家开始组建一个好友组，该组开始游戏，随后从队伍中移除。如此反复，直到队伍为空。形式化地说，如果存在一个数组 $K = [K[0], K[1], \ldots, K[g - 1]]$，使得：

• $g > 0$ 且对于所有 $j$（$0 \leq j < g$），都有 $K[j] > 0$；
• $K[0] + K[1] + \ldots + K[g - 1] = n$；
• 对于每个 $j \in [0, g - 1]$，玩家 $s[j], s[j] + 1, \ldots, s[j] + K[j] - 1$ 构成一个规模为 $K[j]$ 的好友组，其中 $s[0] = 0$，其他情况下 $s[j] = K[0] + K[1] + \ldots + K[j - 1]$；

则称队伍可以被划分为 $g$ 个好友组。

组织者希望 最小化 进行游戏的好友组数量。即，他们希望将队伍划分为 $g$ 个好友组，并且无法再划分为 $g - 1$（或更少）个好友组。

你的任务是找到一种将队伍划分为最少好友组的方案，并输出该划分中各组的规模数组。

实现细节

你需要实现以下函数：

std::vector<int> partition_players(int n, int m, std::vector<int> x, std::vector<int> y)

• $n$：队伍中的玩家数。
• $m$：好友关系的数量。
• $x, y$：长度为 $m$ 的数组，描述好友关系。

该过程应返回一个数组，表示将队伍划分为最少好友组时，各组的规模。

该过程在每个测试用例中仅调用一次。

5 3
0 1
1 4
3 4

3
2 1 2

7 6
0 1
4 5
2 4
1 5
2 5
3 6

5
2 1 1 2 1

Hint

样例解释 1

玩家 $0$ 与 $1$、玩家 $1$ 与 $4$、玩家 $3$ 与 $4$ 是好友。玩家 $2$ 在队伍中没有好友，因此必须单独形成一个规模为 $1$ 的好友组，这意味着好友组的最小数量为 $g = 3$。另一方面，玩家 $0$ 与 $1$，以及玩家 $3$ 与 $4$ 可以各组成一个规模为 $2$ 的好友组。

因此，队伍可被划分为 $3$ 个好友组，规模分别为 $2, 1, 2$。

样例解释 2

玩家 $0$ 与 $1$、$4$ 与 $5$、$2$ 与 $4$、$1$ 与 $5$、$2$ 与 $5$、$3$ 与 $6$ 是好友。玩家 $3$ 的唯一好友是玩家 $6$，因此任何包含玩家 $3$ 的好友组，要么是玩家 $3$ 单独组成的规模为 $1$ 的好友组，要么是包含玩家 $3$ 和 $6$ 的好友组。

后一种情况的好友组必须同时包含玩家 $4$ 和 $5$，但这是不可能的，因为玩家 $6$ 的唯一好友是玩家 $3$，因此玩家 $3$ 无法通过好友链与玩家 $4$ 和 $5$ 相连。因此，玩家 $3$ 必须被放入一个规模为 $1$ 的好友组。

同理，玩家 $6$ 也必须被放入一个规模为 $1$ 的好友组，因此好友组数量至少为 $4$。玩家 $0, 1, 2$ 并不能组成规模为 $3$ 的好友组，因为在该组内，玩家 $0$ 或 $1$ 都无法通过好友链与玩家 $2$ 相连。另一方面，玩家 $0$ 与 $1$，以及玩家 $4$ 与 $5$ 可以分别组成规模为 $2$ 的好友组。

因此，队伍可被划分为 $5$ 个好友组，规模分别为 $2, 1, 1, 2, 1$。

子任务

1. （5 分）对于每个 $i \in [0, m - 1]$，有 $y[i] = x[i] + 1$。
2. （7 分）对于每个 $i \in [0, m - 1]$，有 $y[i] \leq x[i] + 2$。
3. （6 分）$n \leq 300$ 且 $m \leq 600$。
4. （15 分）$n \leq 2000$ 且 $m \leq 4000$。
5. （34 分）不存在好友关系环。即，对于任意满足 $l \geq 3$ 的不同玩家序列 $p[0], p[1], \ldots, p[l - 1]$，若对于每个 $0 \leq j < l - 1$，玩家 $p[j]$ 与 $p[j + 1]$ 是好友，则玩家 $p[0]$ 与 $p[l - 1]$ 不是好友。
6. （16 分）$n \leq 30000$ 且 $m \leq 60000$。
7. （17 分）无额外限制。

数据范围

• $2 \leq n \leq 100000$
• $0 \leq m \leq 200000$
• 对于每个 $i \in [0, m)$，$0 \leq x[i] < y[i] < n$
• 好友关系互不相同。即对于任意 $0 \leq i < j < m$，有 $x[i] \neq x[j]$ 或 $y[i] \neq y[j]$。
• 若存在多种满足最小好友组数量的方案，你可以返回任意一种有效方案。

翻译由 ChatGPT-5 完成