e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Змагання

2015 German Collegiate Programming Contest (GCPC)

Охотник за головами II

Спайк - охотник за головами - отслеживает преступника в космическом пространстве. К счастью для него путешествия через гиперпространства сделало задачу посещения нескольких планет намного проще. Каждая планета имеет ряд астральных ворот; каждые такие ворота соединяется с воротами на другой планете. Эти соединения в гиперпространстве по понятным причинам безопасности являются однонаправленными: ворота с одной планеты являются точкой входа, а ворота с другой планеты - точкой выхода из гиперпространства. Кроме того, сеть гиперпространственных соединений не содержит петель, чтобы предотвратить астральный мир от взрыва - все еще помнят трагический урок аварии ворот в 2022 году, когда была уничтожена большая часть Луны.

Глядя на звездную карту, Спайк задается вопросом: сколько друзей ему следует привести чтобы совершить поиск на каждой планете. Каждая планета должна быть посещена не более чем одним другом, в противном случае преступник может что-то заподозрить и бежать прежде чем его захватят в плен. Каждый человек может начать поиск на любой планете по своему выбору и путешествовать по гиперпространственным соединениям с одной планеты на другую, будучи связанным ограничениями на количество гиперпространственных поездок.

prb7707.gif

Входные данные

Начинается с целого числа n (0 < n1000) - количества планет. Планеты пронумерованы от 0 до n - 1. Следующие n строк задают связи в гиперпространстве. i-ая из этих строк содержит количество связей k (0kn - 1) исходящих из планеты i, за которым следует k целых чисел - планеты назначения.

Выходные данные

Вывести минимальное количество лиц, необходимых для посещения каждой планеты.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
4
1 1
1 2
0
1 1
Вихідні дані #1
2
Вхідні дані #2
6
0
1 2
2 4 5
1 2
0
0
Вихідні дані #2
4
Джерело 2015 German Collegiate Programming Contest (GCPC), June 20, Problem B