G. 随机播放歌曲

时间限制：$3$ 秒 内存限制：$256$ 兆字节

题目描述

Vladislav 的播放列表中有 $n$ 首歌曲，编号为 $1$ 到 $n$。 第 $i$ 首歌曲有流派 $g_i$ 和作者 $w_i$。

他希望制作一个令人兴奋的播放列表： 相邻两首歌必须满足：流派相同 或 作者相同（可都满足）。

不一定能使用全部歌曲，所以分两步操作：

1. 删除尽可能少的歌曲
2. 把剩下的重新排列，使其成为令人兴奋的播放列表

求：最少需要删除多少首歌。

输入格式

第一行一个整数 $t$（$1\le t\le 1000$），表示测试用例数量。

每个测试用例：

• 第一行一个整数 $n$（$1\le n\le 16$）
• 接下来 $n$ 行，每行两个字符串 $g_i, w_i$（仅小写字母）
  • $1\le |g_i|,|w_i|\le 10^4$

保证：

• 所有测试用例的 $2^n$ 总和 $\le 2^{16}$
• 所有字符串总长之和 $\le 4\cdot 10^5$

输出格式

对每个测试用例，输出一个整数： 能构成合法播放列表的前提下，最少删除多少首歌。

样例输入

4
1
pop taylor
4
electronic themotans
electronic cardream
pop themotans
pop irinrim
7
rap eminem
rap dre
rap kanye
pop taylor
indierock arcticmonkeys
indierock arcticmonkeys
punkrock offspring
4
a b
c d
e f
g h

样例输出

0
0
4
3

题目注释（样例解释）

• 测试用例 $1$：只有 $1$ 首歌，合法，删除 $0$ 首。
• 测试用例 $2$：可以排成合法序列，删除 $0$ 首。
• 测试用例 $3$：保留 $3$ 首，删除 $4$ 首。
• 测试用例 $4$：只能保留 $1$ 首，删除 $3$ 首。

需要我马上给你 1950G 官方标程题解 + 可直接 AC 代码 吗？ $n\le 16$ 是经典状压 DP + 哈密顿路径模型。