Ограничение по времени: 2.000 секунд
Ограничение по памяти: 100.000 мегабайт
Юля и Максим решили провести чемпионат по Мафии в Контуре.
Игры решено проводить по следующим правилам. В игре есть две роли - мирные жители и мафия (и тех, и тех может быть несколько). Роли игрокам раздаются в самом начале игры, после чего каждый игрок с ролью мирного жителя знает только свою роль, но не знает роли других игроков, в то время как каждый игрок с ролью мафии знает роли всех других игроков.
Далее играют несколько туров (ночей): каждой ночью некоторые пары игроков встречаются друг с другом. И в конце ночи объявляется одна жертва, которую убила мафия этой ночью. Каждую ночь мафия убивает ровно одного мирного жителя, и это делает ровно один из представителей мафии. Чтобы представитель мафии мог убить мирного жителя, между ними должна была произойти встреча.
Григорий внимательно следил за игрой, поэтому ему известно количество игроков, а также количество и описание всех ночей.
Помогите ему найти минимальное возможное количество представителей мафии в игре, при котором игра могла следовать известному ему сценарию.
В первой строке даны два целых числа k и m - количество игроков и количество ночей в игре (2 ≤ k ≤ 200, 1 ≤ m ≤ 200, 1 ≤ k − m ≤ 15).
Далее идет m блоков - описание ночей. Описание i-й ночи начинается с t блоков описания живых игроков (t - количество игроков, живых на момент начала i-й ночи). Каждый блок состоит из двух строк:
Гарантируется, что все встречи были двусторонними. То есть, если игрок номер a присутствует в списке встреч у игрока номер b, то и игрок b присутствует в списке у игрока a.
В последней строке описания ночи дано целое число v - номер игрока, который был убит этой ночью.
Гарантируется, что входные данные описывают корректную игру.
Выведите одно целое число - минимальное количество игроков, которые должны играть за мафию, чтобы описанная игра могла произойти.
| input | output |
|---|---|
4 2 1 3 2 3 4 2 3 1 3 4 3 3 1 2 4 4 3 1 2 3 1 2 2 3 4 3 2 2 4 4 2 2 3 2 |
1 |