CF1630F Making It Bipartite

给定一个无向图，有 $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 \cdot 10^4$），表示图中顶点的数量。 第二行包含 $n$ 个整数，第 $i$ 个为 $a_i$（$1 \le a_i \le 5 \cdot 10^4$），表示第 $i$ 个顶点的值，所有 $a_i$ 互不相同。 保证所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^4$。

对于每个测试用例，输出一个整数，表示最少需要删除多少个顶点，使得剩下的图是二分图。

在第一个测试用例中，如果我们删除值为 $1$ 和 $2$ 的顶点，剩下的图就是二分图，因此答案为 $2$，不可能删除更少的顶点仍然得到二分图。 BeforeAfter 测试用例 #1 在第二个测试用例中，不需要删除任何顶点，因为图已经是二分图，所以答案为 $0$。 BeforeAfter 测试用例 #2 在第三个测试用例中，只需要删除值为 $12$ 的顶点，因此答案为 $1$。 BeforeAfter 测试用例 #3 在第四个测试用例中，删除值为 $2$ 和 $195$ 的顶点，答案为 $2$。 BeforeAfter 测试用例 #4 由 ChatGPT 4.1 翻译