#P1630F. Making It Bipartite
-
ID: 6272
Type: RemoteJudge
4000ms
512MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
Hydro
Tags> Making It Bipartite
No submission language available for this problem.
Description
You are given an undirected graph of $n$ vertices indexed from $1$ to $n$, where vertex $i$ has a value $a_i$ assigned to it and all values $a_i$ are different. There is an edge between two vertices $u$ and $v$ if either $a_u$ divides $a_v$ or $a_v$ divides $a_u$.
Find the minimum number of vertices to remove such that the remaining graph is bipartite, when you remove a vertex you remove all the edges incident to it.
The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Description of the test cases follows.
The first line of each test case contains a single integer $n$ ($1 \le n \le 5\cdot10^4$) — the number of vertices in the graph.
The second line of each test case contains $n$ integers, the $i$-th of them is the value $a_i$ ($1 \le a_i \le 5\cdot10^4$) assigned to the $i$-th vertex, all values $a_i$ are different.
It is guaranteed that the sum of $n$ over all test cases does not exceed $5\cdot10^4$.
For each test case print a single integer — the minimum number of vertices to remove such that the remaining graph is bipartite.
Input
The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Description of the test cases follows.
The first line of each test case contains a single integer $n$ ($1 \le n \le 5\cdot10^4$) — the number of vertices in the graph.
The second line of each test case contains $n$ integers, the $i$-th of them is the value $a_i$ ($1 \le a_i \le 5\cdot10^4$) assigned to the $i$-th vertex, all values $a_i$ are different.
It is guaranteed that the sum of $n$ over all test cases does not exceed $5\cdot10^4$.
Output
For each test case print a single integer — the minimum number of vertices to remove such that the remaining graph is bipartite.
Samples
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
2
0
1
2
Note
In the first test case if we remove the vertices with values $1$ and $2$ we will obtain a bipartite graph, so the answer is $2$, it is impossible to remove less than $2$ vertices and still obtain a bipartite graph.
| Before | After |
 |  |
In the second test case we do not have to remove any vertex because the graph is already bipartite, so the answer is $0$.
| Before | After |
 |  |
In the third test case we only have to remove the vertex with value $12$, so the answer is $1$.
| Before | After |
 |  |
In the fourth test case we remove the vertices with values $2$ and $195$, so the answer is $2$.
| Before | After |
 |  |