Задачи
Монтеско против Капулето
Монтеско против Капулето
Ромео и Джульетта наконец-то решили пожениться. Но приготовить свадебную вечеринку будет непросто, так как хорошо известно, что их семьи --- Монтеско и Капулето --- являются кровавыми врагами. В этой задаче Вам следует решать, кого пригласить, а кого не пригласить, чтобы предотвратить кровопролитие.
У нас есть список $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
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