codeforces#P1950G. Shuffling Songs
Shuffling Songs
Description
Vladislav has a playlist consisting of songs, numbered from to . Song has genre and writer . 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 and are strings of length no more than .
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.
The first line of the input contains a single integer () — the number of test cases. The description of test cases follows.
The first line of each test case contains a single integer () — the number of songs in the original playlist.
Then lines follow, the -th of which contains two strings of lowercase letters and () — the genre and the writer of the -th song. Where and are lengths of the strings.
The sum of over all test cases does not exceed .
The sum of over all test cases does not exceed .
For each test case, output a single integer — the minimum number of removals necessary so that the resulting playlist can be made exciting.
Input
The first line of the input contains a single integer () — the number of test cases. The description of test cases follows.
The first line of each test case contains a single integer () — the number of songs in the original playlist.
Then lines follow, the -th of which contains two strings of lowercase letters and () — the genre and the writer of the -th song. Where and are lengths of the strings.
The sum of over all test cases does not exceed .
The sum of over all test cases does not exceed .
Output
For each test case, output a single integer — the minimum number of removals necessary so that the resulting playlist can be made exciting.
Note
In the first test case, the playlist is already exciting.
In the second test case, if you have the songs in the order , it is exciting, so you don't need to remove any songs.
In the third test case, you can remove songs . Then the playlist with songs in the order is exciting.