每年，克卢日-纳波卡（Cluj-Napoca）都会举办一场盛大的桌游博览会，展示各种各样的全新游戏。今年的主打项目是一款名为 BoardOina 的游戏。

有 $n$ 名玩家排成一队等待体验游戏。玩家按他们在队列中的顺序从 $0$ 到 $n - 1$ 进行编号。玩家 $0$ 位于队列最前面，玩家 $n - 1$ 位于队列最后面。

队列中的玩家之间存在 $m$ 条不同的双向好友关系。具体来说，对于每个 $0 \le i < m$，玩家 $x[i]$ 和玩家 $y[i]$ 是好友，其中 $0 \le x[i] < y[i] < n$。好友关系是对称的。

考虑队列中从玩家 $s$ 开始的连续 $k$ 个玩家组成的序列（其中 $0 \le s < n$ 且 $1 \le k \le n - s$）。如果这组玩家中的任意两人都可以通过该组内部的一系列好友关系相连，则称这组玩家形成了一个大小为 $k$ 的好友组。具体来说，如果对于满足 $s \le u < v < s + k$ 的每对玩家 $u$ 和 $v$，都存在一个玩家序列 $p[0], \dots, p[l - 1]$ 满足以下条件，则玩家 $s, s + 1, \dots, s + k - 1$ 形成一个大小为 $k$ 的好友组：

• $l \ge 2$；
• 对于每个 $0 \le j < l$，都有 $s \le p[j] < s + k$；
• $p[0] = u$ 且 $p[l - 1] = v$；
• 对于每个 $0 \le j \le l - 2$，玩家 $p[j]$ 和 $p[j + 1]$ 是好友。

注意，在 $k = 1$ 的情况下，玩家 $s$ 独自形成一个大小为 $1$ 的好友组。

BoardOina 可以由任意数量的玩家游玩。然而，为了让游戏更成功，主办方只允许好友组进行游戏。

每次只能有一个小组进行游戏。对于每局游戏，都会从队列最前端的玩家开始形成一个好友组并开始游戏。该好友组中的玩家随后将从队列中移除。这个过程会一直重复，直到队列变空。正式地，如果存在一个表示各组大小的数组 $K = [K[0], K[1], \dots, K[g - 1]]$ 满足以下所有条件，我们称队列可以被划分为 $g$ 个好友组：

• $g > 0$ 且对于每个 $0 \le j < g$，都有 $K[j] > 0$；
• $K[0] + K[1] + \dots + K[g - 1] = n$；
• 对于每个 $0 \le j < g$，玩家 $s[j], s[j] + 1, \dots, s[j] + K[j] - 1$ 形成一个大小为 $K[j]$ 的好友组，其中 $s[0] = 0$，对于 $j > 0$ 有 $s[j] = K[0] + K[1] + \dots + 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 的数组，描述好友关系。对于每个 $0 \le i < m$，玩家 X[i] 和 Y[i] 是好友。
• 该函数应返回一个表示各组大小的数组，代表将玩家队列划分为最少数量好友组的一种方案。
• 对于每个测试用例，该函数将被恰好调用一次。

数据范围

• $2 \le n \le 100\,000$
• $0 \le m \le 200\,000$
• 对于每个 $0 \le i < m$，都有 $0 \le X[i] < Y[i] < n$。
• 好友关系是两两不同的。换句话说，对于任意 $0 \le i < j < m$，都有 $X[i] \ne X[j]$ 或 $Y[i] \ne Y[j]$。
• 如果存在多种具有最少组数的解，你可以返回其中任意一种合法解。

子任务

1. (5 分) 对于每个 $0 \le i < m$，都有 $Y[i] = X[i] + 1$。
2. (7 分) 对于每个 $0 \le i < m$，都有 $Y[i] \le X[i] + 2$。
3. (6 分) $n \le 300$ 且 $m \le 600$。
4. (15 分) $n \le 2\,000$ 且 $m \le 4\,000$。
5. (34 分) 不存在环状的好友关系。也就是说，对于任意长度 $l \ge 3$ 且由互不相同的玩家组成的序列 $p[0], p[1], \dots, p[l - 1]$，如果对于每个 $0 \le j < l - 1$，玩家 $p[j]$ 和 $p[j + 1]$ 都是好友，那么玩家 $p[0]$ 和 $p[l - 1]$ 不是好友。
6. (16 分) $n \le 30\,000$ 且 $m \le 60\,000$。
7. (17 分) 无附加限制。

样例

样例输入 1

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

样例输出 1

[2, 1, 2]

样例说明 1

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

玩家 $2$ 在队列中没有好友，因此必须由玩家 $2$ 独自组成一个好友组，这意味着最少的好友组数量 $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})

样例输出 2

[2, 1, 1, 2, 1]

样例说明 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$ 相连。如果玩家 $5$ 也在该组中，情况就会有所不同，但由于玩家 $3$ 和 $4$ 必然在不同的组中，这永远不会发生。因此，划分中的好友组数量至少为 $5$。

另一方面，玩家 $0$ 和 $1$、以及玩家 $4$ 和 $5$ 形成了两个大小为 $2$ 的好友组。因此，队列可以被划分为 $5$ 个大小分别为 $2, 1, 1, 2, 1$ 的好友组。函数可以返回 [2, 1, 1, 2, 1]。

评测程序示例

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

• 第 $1$ 行：n m
• 第 $2 + i$ 行（$0 \le i < m$）：X[i] Y[i]

令 partition_players 返回的数组元素为 $K[0], K[1], \dots, K[g - 1]$，其中 $g$ 为某个非负整数。样例评测程序将按以下格式输出：

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