Shuffling Songs
Contest: Codeforces Round 937 (Div. 4)
Difficulty rating: 1900
Tags: bitmasks, dfs and similar, dp, graphs, hashing, implementation, strings

Vladislav has a playlist consisting of $$$n$$$ songs, numbered from $$$1$$$ to $$$n$$$. Song $$$i$$$ has genre $$$g_i$$$ and writer $$$w_i$$$. He wants to make a playlist in such a way that every pair of adjacent songs either have the same writer or are from the same genre (or both). He calls such a playlist exciting. Both $$$g_i$$$ and $$$w_i$$$ are strings of length no more than $$$10^4$$$.

It might not always be possible to make an exciting playlist using all the songs, so the shuffling process occurs in two steps. First, some amount (possibly zero) of the songs are removed, and then the remaining songs in the playlist are rearranged to make it exciting.

Since Vladislav doesn't like when songs get removed from his playlist, he wants the making playlist to perform as few removals as possible. Help him find the minimum number of removals that need to be performed in order to be able to rearrange the rest of the songs to make the playlist exciting.

Input format:
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 16$$$) — the number of songs in the original playlist.

Then $$$n$$$ lines follow, the $$$i$$$-th of which contains two strings of lowercase letters $$$g_i$$$ and $$$w_i$$$ ($$$1 \leq |g_i|, |w_i| \leq 10^4$$$) — the genre and the writer of the $$$i$$$-th song. Where $$$|g_i|$$$ and $$$|w_i|$$$ are lengths of the strings.

The sum of $$$2^n$$$ over all test cases does not exceed $$$2^{16}$$$.

The sum of $$$|g_i| + |w_i|$$$ over all test cases does not exceed $$$4 \cdot 10^5$$$.

Output format:
For each test case, output a single integer — the minimum number of removals necessary so that the resulting playlist can be made exciting.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the playlist is already exciting.

In the second test case, if you have the songs in the order $$$4, 3, 1, 2$$$, it is exciting, so you don't need to remove any songs.

In the third test case, you can remove songs $$$4, 5, 6, 7$$$. Then the playlist with songs in the order $$$1, 2, 3$$$ is exciting.

Example input:
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

Example output:
0
0
4
3

Editorial:
First of all, always comparing strings takes quite a long time, so, let's map the strings to integers. We can do that by keeping all strings in some array, sorting the array, and mapping each string to its position in the array. This process is called "Normalization" or "Coordinate Compression".
Now, we can do a dynamic programming solution over subsets.
We denote mask as our current bit-mask and we say it has the value of all elements we include. For example, if our mask is equal to 7, in binary it looks like ...000111, so we can say that we included elements 0, 1 and 2. Each power of two set in our mask, implies we include that element.
So now, if we iterate over masks and the last included element, we can mark $$$dp_{mask, i}$$$ as a boolean which tells whether it is possible to get to this state. We transition from a state to another by using the current mask and trying to include all non-included elements one-by-one, and checking out if it is possible to include them. If it is, we update our new mask.
After calculating for each state whether we can get to it, using previously calculated states, we update our answer as the maximum number of included elements (bits set) in a mask which is obtainable.