注意事项

请在提交源代码前添加 #include "boardgames.h"。

题目描述

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

有 $n$ 名玩家排成一队，等待尝试这款游戏。玩家按照队列顺序编号为 $0$ 到 $n-1$。玩家 $0$ 在队列最前面，玩家 $n-1$ 在队列最后面。

队列中有 $m$ 个不同的友谊关系，涉及 $m$ 对玩家。具体来说，对于从 $0$ 到 $m-1$ 的每个 $i$，玩家 $x[i]$ 和玩家 $y[i]$ 是朋友，其中 $0 \leq x[i] < y[i] < n$。友谊关系是对称的。

考虑队列中从玩家 $s$ 开始的 $k$ 个连续玩家序列（对于任意 $s$ 和 $k$，满足 $0 \leq s < n$ 且 $1 \leq k \leq n-s$）。如果对于该序列中的任意两个玩家，他们通过该朋友组内的友谊关系序列相连，则该玩家序列形成一个大小为 $k$ 的朋友组。具体来说，玩家 $s, s+1, \ldots, s+k-1$ 形成一个大小为 $k$ 的朋友组，如果对于每个 $u$ 和 $v$（满足 $s \leq u < v < s+k$），存在一个玩家序列 $p[0], \ldots, p[l-1]$，满足：

• $l \geq 2$；
• 对于每个 $j$（从 $0$ 到 $l-1$），$s \leq p[j] < s+k$；
• $p[0] = u$ 且 $p[l-1] = v$；
• 对于每个 $j$（从 $0$ 到 $l-2$），玩家 $p[j]$ 和 $p[j+1]$ 是朋友。

注意，当 $k = 1$ 时，玩家 $s$ 单独形成一个大小为 $1$ 的朋友组。

BoardOina 可以由任意数量的玩家游玩。然而，为了使游戏更成功，组织者只允许朋友组参与游戏。

一次只能有一个组玩游戏。对于每场游戏，从队列最前面的玩家开始形成一个朋友组，并开始玩游戏。该朋友组中的玩家从队列中移除。重复此过程，直到队列变空为止。形式上，我们说队列可以被分成 $g$ 个朋友组，如果存在一个组大小数组 $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$（从 $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-1$ 个（或更少）朋友组。

你的任务是找到一个将队列分成最少朋友组的分组方式，并报告组大小数组。

实现细节

你应该实现以下程序：

std::vector<int> partition_players(int n, int m, std::vector<int> X, std::vector<int> Y)

• $n$：队列中的玩家数量。
• $m$：友谊关系的数量。
• $X$, $Y$：长度为 $m$ 的数组，描述友谊关系。
• 该程序应返回一个组大小数组，表示将玩家队列分成最少数量的朋友组。
• 对于每个测试点，该程序只被调用一次。

示例评测程序

示例评测程序读取以下格式的输入：

• 第 $1$ 行：$n\ m$
• 第 $2 + i$ $(0 \leq i < m)$ 行：$x[i]\ y[i]$

设 partition_players 返回的数组元素为 $K[0], K[1], \ldots, K[g-1]$，其中 $g$ 为非负数。示例评测程序的输出格式如下：

• 第 $1$ 行：$g$
• 第 $2$ 行：$K[0]\ K[1]\ \ldots\ K[g-1]$

样例 1

考虑以下调用：

partition_players(5, 3, {0, 1, 3}, {1, 4, 4})

在这个示例中，玩家 $0$ 和 $1$、玩家 $1$ 和 $4$、以及玩家 $3$ 和 $4$ 是朋友。

玩家 $2$ 在队列中没有朋友，因此必须单独形成一个大小为 $1$ 的朋友组，这意味着最少朋友组数量为 $g = 3$。另一方面，玩家 $0$ 和 $1$，以及玩家 $3$ 和 $4$ 可以形成大小为 $2$ 的朋友组。

因此，队列可以被分成 $3$ 个朋友组，大小分别为 $2$、$1$ 和 $2$，所以程序可以返回 [2, 1, 2]。

样例 2

考虑以下调用：

partition_players(7, 6, {0, 4, 2, 1, 2, 3}, {1, 5, 4, 5, 5, 6})

在这个示例中，玩家 $0$ 和 $1$、玩家 $4$ 和 $5$、玩家 $2$ 和 $4$、玩家 $1$ 和 $5$、玩家 $2$ 和 $5$ 以及玩家 $3$ 和 $6$ 是朋友。

玩家 $3$ 的唯一朋友是玩家 $6$，因此任何包含玩家 $3$ 的朋友组要么是：

• 大小为 $1$ 的朋友组，仅包含玩家 $3$；
• 包含玩家 $3$ 和玩家 $6$ 的朋友组。

在第二种情况下，朋友组还必须包含玩家 $4$ 和 $5$。这是不可能的，因为玩家 $6$ 的唯一朋友是玩家 $3$，所以玩家 $3$ 无法通过友谊关系序列与玩家 $4$ 和 $5$ 相连。

因此，玩家 $3$ 必须被放入一个大小为 $1$ 的朋友组。类似地，玩家 $6$ 也必须被放入一个大小为 $1$ 的朋友组，因此分组中的朋友组数量至少为 $4$。

玩家 $0$、$1$ 和 $2$ 无法形成一个大小为 $3$ 的朋友组，因为玩家 $0$ 或 $1$ 无法通过组内的友谊关系序列与玩家 $2$ 相连。如果组内有玩家 $5$，情况可能不同，但由于玩家 $3$ 和 $4$ 肯定会在不同的组中，这种情况不会发生。也就是说，分组中的朋友组数量至少为 $5$。

另一方面，玩家 $0$ 和 $1$，以及玩家 $4$ 和 $5$ 可以形成两个大小为 $2$ 的朋友组。

因此，队列可以被分成 $5$ 个朋友组，大小分别为 $2$、$1$、$1$、$2$ 和 $1$。程序可以返回 [2, 1, 1, 2, 1]。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq n \leq 100\,000$
• $0 \leq m \leq 200\,000$
• 对于每个 $i$ $(0 \leq i < m)$，$0 \leq x[i] < y[i] < n$
• 友谊关系是不同的。换句话说，对于每个 $i$ 和 $j$ $(0 \leq i < j < m)$，$x[i] \neq x[j]$ 或 $y[i] \neq y[j]$
• 如果存在多个具有最小组数量的答案，你可以返回任意一个合法的答案。

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$5$	对于每个 $i$（从 $0$ 到 $m-1$），$y[i] = x[i] + 1$
$2$	$7$	对于每个 $i$（从 $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$	没有循环的友谊关系。即，对于任意不同的玩家序列 $p[0], p[1], \ldots, p[l-1]$ $(l \geq 3)$，如果对于每个 $0 \leq j < l-1$，玩家 $p[j]$ 和 $p[j+1]$ 是朋友，则玩家 $p[0]$ 和 $p[l-1]$ 不是朋友。
$6$	$33$	无附加限制