Гра в Мафію
Фінеас і Ферб вирішили організувати чемпіонат з гри в Мафію в Денвіллі.
У цій грі є дві ролі: мирні жителі та мафія (кожної ролі може бути кілька гравців). На початку гри кожен гравець отримує свою роль: мирні жителі знають лише свою роль, але не знають ролей інших, тоді як мафія знає ролі всіх учасників.
Гра триває кілька турів (ночей): кожної ночі деякі пари гравців зустрічаються. Наприкінці ночі оголошується одна жертва, яку вбила мафія. Щоночі мафія вбиває рівно одного мирного жителя, і це робить один з представників мафії. Для того, щоб мафія могла вбити мирного жителя, між ними повинна була відбутися зустріч.
Кендис спостерігала за грою, тому їй відома кількість гравців, а також кількість і опис усіх ночей.
Допоможіть їй визначити мінімальну можливу кількість представників мафії, при якій гра могла б відбутися за відомим їй сценарієм, щоб вона могла розповісти мамі про небезпечну діяльність Фінеаса і Ферба.
Вхідні дані
У першому рядку дано два цілих числа k і m (2 ≤ k ≤ 200, 1 ≤ m ≤ 200, 1 ≤ k - m ≤ 15) — кількість гравців і кількість ночей у грі.
Далі йде m блоків опису ночей. Опис i-ї ночі починається з t блоків опису живих гравців (t — кількість гравців, які залишилися живими на початок i-ї ночі). Кожен блок складається з двох рядків:
У першому рядку дано два цілих числа n і c (1 ≤ n ≤ k, 0 ≤ c ≤ t - 1) — номер гравця і кількість його зустрічей цієї ночі.
У другому рядку наведено c натуральних чисел — номери гравців, з якими зустрівся гравець під номером n.
Гарантується, що всі зустрічі були двосторонніми. Тобто, якщо гравець номер a присутній у списку зустрічей у гравця номер b, то і гравець b присутній у списку у гравця a.
В останньому рядку опису ночі дано ціле число v — номер гравця, який був убитий цієї ночі. Гарантується, що вхідні дані описують коректну гру.
Вихідні дані
Виведіть одне ціле число — мінімальну кількість гравців, які повинні грати за мафію, щоб описана гра могла відбутися.