← 返回题目列表

Codeforces · 1630/F

F. 使其成为二分式

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

给您一个无向图,其中 $$$n$$$ 个顶点的索引从 $$$1$$$ 到 $$$n$$$,其中顶点 $$$i$$$ 分配了一个值 $$$a_i$$$,并且所有值 $$$a_i$$$ 都不同。如果 $$$a_u$$$ 整除 $$$a_v$$$ 或 $$$a_v$$$ 整除 $$$a_u$$$,则两个顶点 $$$u$$$ 和 $$$v$$$ 之间有一条边。

找到要删除的最小顶点数,使得剩余图是二分图,当您删除一个顶点时,您将删除与其关联的所有边。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5\cdot10^4$$$) — 图中的顶点数。

每个测试用例的第二行包含 $$$n$$$ 个整数,其中第 $$$i$$$ 是分配给第 $$$i$$$ 个顶点的值 $$$a_i$$$ ($$$1 \le a_i \le 5\cdot10^4$$$),所有值 $$$a_i$$$ 都不同。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$5\cdot10^4$$$。

输出

对于每个测试用例,打印一个整数 - 要删除的最小顶点数,以便剩余图是二分图。

示例

输入 #1

4
4
8 4 2 1
4
30 2 3 5
5
12 4 6 2 3
10
85 195 5 39 3 13 266 154 14 2

输出 #1

2
0
1
2

注意

在第一个测试用例中,如果我们删除值为 $$$1$$$ 和 $$$2$$$ 的顶点,我们将获得一个二分图,所以答案是 $$$2$$$,不可能删除少于 $$$2$$$ 的顶点并仍然获得二分图。

BeforeAfter测试用例#1

在第二个测试用例中,我们不必删除任何顶点,因为图已经是二分图,所以答案是 $$$0$$$。

BeforeAfter测试用例#2

在第三个测试用例中,我们只需删除值为 $$$12$$$ 的顶点,因此答案是 $$$1$$$。

BeforeAfter测试用例#3

在第四个测试用例中,我们删除了值为 $$$2$$$ 和 $$$195$$$ 的顶点,所以答案是 $$$2$$$。

BeforeAfter测试用例#4