1950G - Shuffling Songs - CodeForces Solution

import sys
from functools import lru_cache
input = sys.stdin.readline

def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(list(s[:len(s) - 1]))
def invr():
    return(map(int,input().split()))

def bit_length(i):
    s = bin(i)           s = s.lstrip('-0b')     return len(s)

def main():
    m = inp()
    lis = []
    for _ in range(m):
        lis.append(input().split())
    edge = [[0] * m for _ in range(m)]
    for i in range(m):
        for j in range(i + 1, m):
            if lis[i][0] == lis[j][0] or lis[i][1] == lis[j][1]:
                edge[i][j] = 1
                edge[j][i] = 1

    @lru_cache(None)
    def dfs(mask, last = -1):
        tmp  = 0
        for i in range(m):
            if last == -1:
                tmp = max(tmp, dfs(mask | (1 << i), i))

            elif mask & (1 << i) == 0 and edge[last][i] == 1:
                tmp = max(tmp, dfs(mask | (1 << i), i))
        return tmp if tmp != 0 else bin(mask).count('1')


    
    print(m - dfs(0))


if __name__ == "__main__":
    n = inp()
    for i in range(n):
        main()