← 返回题目列表

Codeforces · 1950/G

G. 随机播放歌曲

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

Vladislav 的播放列表由 $$$n$$$ 歌曲组成,编号从 $$$1$$$ 到 $$$n$$$。歌曲 $$$i$$$ 的流派为 $$$g_i$$$,作者为 $$$w_i$$$。他希望制作一个播放列表,使得每对相邻的歌曲要么具有相同的作者,要么来自相同的流派(或两者)。他称这样的播放列表令人兴奋。 $$$g_i$$$ 和 $$$w_i$$$ 都是长度不超过 $$$10^4$$$ 的字符串。

可能并不总是能够使用所有歌曲制作令人兴奋的播放列表,因此随机播放过程分两步进行。首先,删除一定数量(可能为零)的歌曲,然后重新排列播放列表中的剩余歌曲以使其令人兴奋。

由于 Vladislav 不喜欢歌曲从他的播放列表中删除,因此他希望制作播放列表执行尽可能少的删除操作。帮助他找到需要执行的最少删除次数,以便能够重新排列其余歌曲,使播放列表变得令人兴奋。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 16$$$) — 原始播放列表中的歌曲数量。

接下来是 $$$n$$$ 行,其中第 $$$i$$$ 包含两串小写字母 $$$g_i$$$ 和 $$$w_i$$$ ($$$1 \leq |g_i|, |w_i| \leq 10^4$$$) — 第 $$$i$$$ 歌曲的流派和作者。其中 $$$|g_i|$$$ 和 $$$|w_i|$$$ 是字符串的长度。

所有测试用例的 $$$2^n$$$ 总和不超过 $$$2^{16}$$$。

$$$|g_i| 的总和+ |w_i|$$$ 所有测试用例不超过 $$$4 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - 使生成的播放列表令人兴奋所需的最小删除次数。

示例

输入 #1

4
1
pop taylorswift
4
electronic themotans
electronic carlasdreams
pop themotans
pop irinarimes
7
rap eminem
rap drdre
rap kanyewest
pop taylorswift
indierock arcticmonkeys
indierock arcticmonkeys
punkrock theoffspring
4
a b
c d
e f
g h

输出 #1

0
0
4
3

注意

在第一个测试用例中,播放列表已经令人兴奋。

在第二个测试用例中,如果您的歌曲顺序为 $$$4, 3, 1, 2$$$,那就很令人兴奋,因此您不需要删除任何歌曲。

在第三个测试用例中,您可以删除歌曲 $$$4, 5, 6, 7$$$。然后播放列表中的歌曲顺序为 $$$1, 2, 3$$$ 令人兴奋。