色图
题号:NC219669
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

给定n个点m条边的无向图,每个点被赋予了一种颜色,
现在你需要将图中的若干边剪掉,使得图分成若干个互不相连的子图,每个子图中所有点的颜色相同。
你需要计算出最少需要剪掉多少条边,同时输出在最优剪法下每个子图的大小。

输入描述:

第一行输入n,m,表示点的数量和边的数量。(1<=n,m<=2e5)
接下来一行给出n个数,第i个数表示第i个点的颜色c[i]。(1<=c[i]<=1e5)
接下来m行,每行给出两个数x和y,表示点x和点y之间有一条边。

输出描述:

第一行输出将色图分割开所需的最小操作次数。
第二行输出最优剪法下,子图的数量。
第三行输出每个子图的大小,要求将子图大小从小到大排序后输出。

如果有多种解法,输出任意一种皆可。
示例1

输入

复制
2 1
1 2
1 2

输出

复制
1
2
1 1

说明

将点1和点2之间的边剪掉即可。
剪掉之后图会被分成两个大小为1的子图。