#P18624. Kawa Exam
Kawa Exam
Kawa Exam
BaoBao 正在参加 Kawa 编程语言的在线考试,考试包含 道选择题。每道题有 个可选选项,且恰有一个正确选项。作为著名 open-kdk 的活跃贡献者,BaoBao 知道每道题的正确答案:第 道题的正确选项为 。
然而,考试系统有 个 bug。第 个 bug 用 表示:只要这个 bug 尚未修复,BaoBao 就必须在第 道题和第 道题选择相同的选项,即使因此答错也不例外。所有尚未修复的 bug 的约束同时生效。
开发者只有时间修复一个 bug。对于每个 ,请分别计算:如果只修复第 个 bug,BaoBao 最多能够答对多少道题?这些情况彼此独立,每次只移除指定的一个 bug。
输入格式
第一行包含整数 ,表示测试用例数。
每个测试用例的第一行包含两个整数 ,表示题目数和 bug 数。
第二行包含 个整数 ,表示各题的正确选项。
接下来 行,第 行包含两个整数 ,表示第 个 bug。输入没有要求 ,也没有要求不同 bug 的端点对不同。
数据范围
- ;
- ;
- ;
- 一个输入文件中,所有测试用例的 之和不超过 , 之和也不超过 。
输出格式
对每个测试用例输出一行,按原 bug 编号顺序输出 个整数 ,相邻整数之间用一个空格分隔。其中 是只修复第 个 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题。