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