#PQJ1189x6167. QOJ 1189_6167

    ID: 2559 传统题 2000ms 1024MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:FJOI 2020并查集

QOJ 1189_6167

染色图的联通性问题:给定一张 𝑁 个点 𝑀 条边的无向图,顶点标号为 1 , 2 , ⋯ , 𝑁 ,每个点有一个颜色 𝑐 𝑖 。对于每个 𝑖

1 , 2 , ⋯ , 𝑁 ,求出如果删去和顶点 𝑖 相邻的边,剩下的图里有多少对颜色相同的点处在不同联通快中。

输入格式

输入的第一行包含两个整数 𝑁 , 𝑀 。

接下来一行包含 𝑁 个整数 𝑐 1 , 𝑐 2 , ⋯ , 𝑐 𝑁 。

接下来 𝑀 行,每行两个整数 𝑥 , 𝑦 ,描述一条边。

输出格式

输出 𝑛 行,每行一个整数。其中第 𝑖 行的整数表示删去点 𝑖 的答案。

样例数据 样例输入 9 16 2 7 3 2 1 1 1 3 4 1 2 4 2 2 7 1 7 3 6 1 3 1 4 1 5 5 2 样例输出 4 1 3 2 3 3 3 1 1 子任务

对于 20 % 的数据, 𝑁 ≤ 1 000 。

对于 100 % 的数据, 1 ≤ 𝑁 , 𝑀 ≤ 5 × 10 5 , 1 ≤ 𝑐 𝑖 ≤ 𝑁 。

注 赛时并未提供空间限制,“请选手自行评估” QOJ 上设置为 1 GB。