Социальная реклама
Вы решили создать новую социальную сеть. Поскольку другие популярные сети уже имеют миллиарды пользователей, единственный способ конкурировать с ними — предложить уникальные функции, которых нет у других.
Ваша компания решила предложить рекламодателям более доступный способ оплаты за рекламу. Рекламодатель выбирает, на чьей "стене" пользователей будут размещены объявления, и оплачивает только эти объявления. Когда объявление появляется на стене пользователя, его друзья (и сам пользователь) видят это объявление. Таким образом, рекламодатель может заплатить за меньшее количество объявлений, чтобы охватить больше пользователей.
Ваша задача — разместить объявления для определенной группы пользователей с минимальными затратами. У вас есть "список друзей" каждого пользователя, и вы хотите определить минимальное количество объявлений, необходимых для охвата всех пользователей в группе. В этой социальной сети, если A является другом B, то B также является другом A для любых двух пользователей A и B.
Входные данные
Входные данные состоят из нескольких тестов. Первая строка содержит одно целое число, не более 10, указывающее количество тестов. Каждый тест начинается со строки с целым числом n (1 ≤ n ≤ 20), обозначающим количество пользователей в группе. В следующих n строках i-я строка содержит список друзей пользователя i (пользователи обозначены 1, ..., n). Каждая строка начинается с целого числа d (0 ≤ d < n), за которым следуют d номеров друзей. Ни один пользователь не является другом самому себе.
Выходные данные
Для каждого теста выведите в отдельной строке минимальное количество объявлений, необходимых для охвата всей группы пользователей.