← 返回题目列表

Codeforces · 1701/C

C. 日程管理

中文机器翻译题面 查看原题

有 $$$n$$$ 工作人员和 $$$m$$$ 任务。工人的编号从 $$$1$$$ 到 $$$n$$$。每个任务$$$i$$$都有一个值$$$a_i$$$——精通该任务的工人的索引。

每个任务都应该分配一个工作人员。如果工人精通该任务,他们会在 $$$1$$$ 小时内完成。否则,他们需要花费 $$$2$$$ 小时。

工作人员并行工作,彼此独立。每个工人一次只能完成一项任务。

将工作人员分配给所有任务,以便尽早完成任务。工作于时间 $$$0$$$ 开始。完成所有任务的最短时间是多少?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le m \le 2 \cdot 10^5$$$) - 工作人员数量和任务数量。

第二行包含 $$$m$$$ 整数 $$$a_1, a_2, \dots, a_m$$$ ($$$1 \le a_i \le n$$$) — 精通第 $$$i$$$ 任务的工作人员的索引。

所有测试用例的 $$$m$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - 所有任务可以完成的最短时间。

示例

输入 #1

4
2 4
1 2 1 2
2 4
1 1 1 1
5 5
5 1 3 2 4
1 1
1

输出 #1

2
3
1
1

注意

在第一个测试用例中,第一个工作人员处理任务 $$$1$$$ 和 $$$3$$$,第二个工作人员处理任务 $$$2$$$ 和 $$$4$$$。由于他们都精通相应的任务,因此他们每人花费 $$$1$$$ 小时。他们两人都在 $$$2$$$ 小时内完成了 $$$2$$$ 任务。因此,所有任务均在 $$$2$$$ 小时内完成。

在第二个测试用例中,最好将第一个工作人员分配给任务 $$$1、2$$$ 和 $$$3$$$,将第二个工作人员分配给任务 $$$4$$$。第一个工作人员花费 $$$3$$$ 小时,第二个工作人员花费 $$$2$$$ 小时(因为他们不精通所承担的任务)。

在第三个示例中,每个工人都可以被分配到他们擅长的任务。因此,他们每个人都在 $$$1$$$ 小时内完成了任务。