#P18624. Kawa Exam

Kawa Exam

Kawa Exam

BaoBao 正在参加 Kawa 编程语言的在线考试,考试包含 nn 道选择题。每道题有 10510^5 个可选选项,且恰有一个正确选项。作为著名 open-kdk 的活跃贡献者,BaoBao 知道每道题的正确答案:第 ii 道题的正确选项为 aia_i。

然而,考试系统有 mm 个 bug。第 ii 个 bug 用 (ui,vi)(u_i,v_i) 表示:只要这个 bug 尚未修复,BaoBao 就必须在第 uiu_i 道题和第 viv_i 道题选择相同的选项,即使因此答错也不例外。所有尚未修复的 bug 的约束同时生效。

开发者只有时间修复一个 bug。对于每个 1≤i≤m1\le i\le m,请分别计算:如果只修复第 ii 个 bug,BaoBao 最多能够答对多少道题?这些情况彼此独立,每次只移除指定的一个 bug。

输入格式

第一行包含整数 TT,表示测试用例数。

每个测试用例的第一行包含两个整数 n,mn,m,表示题目数和 bug 数。

第二行包含 nn 个整数 a1,…,ana_1,\ldots,a_n,表示各题的正确选项。

接下来 mm 行,第 ii 行包含两个整数 ui,viu_i,v_i,表示第 ii 个 bug。输入没有要求 ui≠viu_i\ne v_i,也没有要求不同 bug 的端点对不同。

数据范围

  • 1≤n,m≤1051\le n,m\le10^5;
  • 1≤ai≤1051\le a_i\le10^5;
  • 1≤ui,vi≤n1\le u_i,v_i\le n;
  • 一个输入文件中,所有测试用例的 nn 之和不超过 10610^6,mm 之和也不超过 10610^6。

输出格式

对每个测试用例输出一行,按原 bug 编号顺序输出 mm 个整数 c1,…,cmc_1,\ldots,c_m,相邻整数之间用一个空格分隔。其中 cic_i 是只修复第 ii 个 bug 时最多能答对的题数。

请不要在每行末尾输出额外空格,原题说明这可能导致答案被判为错误。

样例输入 1

3
7 5
1 2 1 2 1 2 1
1 2
1 3
2 4
5 6
5 7
3 3
1 2 3
1 2
1 3
2 3
2 3
12345 54321
1 2
1 2
1 1

样例输出 1

6 5 5 5 4
1 1 1
1 1 1

样例解释

第一个测试用例中,下面给出修复各个 bug 后一种最优选项向量。向量中的第j项是 BaoBao 对第j题实际选择的选项。

修复的bug编号 一种最优的实际选项向量 答对题数
1 (1,2,1,2,1,1,1) 6
2 (2,2,1,2,1,1,1) 5
3 (1,1,1,2,1,1,1)
4 (1,1,1,1,1,2,1)
5 (1,1,1,1,1,1,1) 4

第二个测试用例中,无论修复哪一个 bug,剩下的两个约束仍然使三道题必须选择相同选项。三道题的正确答案各不相同,因此最多答对1题。

第三个测试用例中,即使修复第一个 bug,第二个 bug 仍然要求两道题选项相同;反之亦然。自约束的第三个 bug 不会改变可行选择。三种情况都只能答对1题。