eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Монтеско против Капулето

Монтеско против Капулето

Ромео и Джульетта наконец-то решили пожениться. Но приготовить свадебную вечеринку будет непросто, так как хорошо известно, что их семьи --- Монтеско и Капулето --- являются кровавыми врагами. В этой задаче Вам следует решать, кого пригласить, а кого не пригласить, чтобы предотвратить кровопролитие. У нас есть список $n$ людей, которых можно пригласить на вечеринку или нет. Для каждого человека $i$ известен список его врагов: $e_1, e_2, ..., e_p$. Отношения "враги" обладают следующими свойствами: \begin{itemize} \item \textbf{Антитранзитивность}. Если $a$ враг $b$, а $b$ враг $c$, то $a$ друг $c$. Кроме того, враги друзей $a$ --- его враги, а друзья друзей $a$ --- его друзья. \item \textbf{Симметричность}. Если $a$ является врагом $b$, то $b$ является врагом $a$ (хотя это может быть и не указано в его списке врагов). \end{itemize} Один человек примет приглашение на вечеринку, если и только если он приглашен, приглашены все его друзья и никто из его врагов не приглашен. Вы должны найти максимальное количество людей, которых можно пригласить, чтобы все они приняли приглашение. Например, если $n = 5$, и мы знаем, что: $1$ --- враг $3, 2$ --- враг $1$ и $4$ --- враг $5$, тогда мы можем пригласить максимум $3$ человек. Этими людьми могут быть $2, 3$ и $4$, но для этой задачи нам нужно только количество приглашенных людей. \InputFile Первая строка содержит количество тестов $m$. Далее следует пустая строка. Пустая строка также используется для разделения тестов. Первая строка каждого теста содержит количество людей $n~(n \le 200)$. Для каждого из этих $n$ людей имеется строка со списком его врагов. Первая строка содержит список врагов человека $1$, вторая строка содержит список врагов человека $2$ и так далее. Каждый список врагов начинается с целого числа $p$ (количество известных врагов этого человека), за которым следуют $p$ целых чисел ($p$ врагов этого человека). Так, например, если враги человека $5$ и $7$, то список его врагов выглядит так: $2 5 7$. \OutputFile Для каждого теста выведите одну строку, содержащей целое число --- максимальное количество людей, которых можно пригласить так, чтобы все они приняли приглашение.
Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
3

5
1 3
1 1
0
1 5
0

8
2 4 5
2 1 3
0
0
0
1 3
0
1 5

3
2 2 3
1 3
1 1
Выходные данные #1
3
5
0