Ромео и Джульетта наконец-то решили пожениться. Но приготовить свадебную вечеринку будет непросто, так как хорошо известно, что их семьи — Монтеско и Капулето — являются кровавыми врагами. В этой задаче Вам следует решать, кого пригласить, а кого не пригласить, чтобы предотвратить кровопролитие.
У нас есть список людей, которых можно пригласить на вечеринку или нет. Для каждого человека известен список его врагов: . Отношения "враги" обладают следующими свойствами:
Антитранзитивность. Если враг , а враг , то друг . Кроме того, враги друзей — его враги, а друзья друзей — его друзья.
Симметричность. Если является врагом , то является врагом (хотя это может быть и не указано в его списке врагов).
Один человек примет приглашение на вечеринку, если и только если он приглашен, приглашены все его друзья и никто из его врагов не приглашен. Вы должны найти максимальное количество людей, которых можно пригласить, чтобы все они приняли приглашение.
Например, если , и мы знаем, что: — враг — враг и — враг , тогда мы можем пригласить максимум человек. Этими людьми могут быть и , но для этой задачи нам нужно только количество приглашенных людей.
Первая строка содержит количество тестов . Далее следует пустая строка. Пустая строка также используется для разделения тестов. Первая строка каждого теста содержит количество людей . Для каждого из этих людей имеется строка со списком его врагов. Первая строка содержит список врагов человека , вторая строка содержит список врагов человека и так далее. Каждый список врагов начинается с целого числа (количество известных врагов этого человека), за которым следуют целых чисел ( врагов этого человека). Так, например, если враги человека и , то список его врагов выглядит так: .
Для каждого теста выведите одну строку, содержащей целое число — максимальное количество людей, которых можно пригласить так, чтобы все они приняли приглашение.