Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 






Кактусы все еще в моде

Задачу добавил: alef

Успешно сдано решений: 9

Возле компьютера Бориса Воротова живет-поживает кактус. Ему (кактусу) рядом с компьютером Бориса весьма комфортно, и он быстро разрастается. Периодически Борис пересаживает кактус и раздает "отводки". В распространении кактусов Борису помогают его друзья и знакомые, тем более, что фирма "Фабрика классов" расположена в крупном офис-центре. Некоторая проблема состоит в том, что все, кто знаком с Борисом не более, чем "через" K человек, уже обзавелись такими кактусами. Сейчас пришло время очередной пересадки, и Борис хотел бы выяснить, сколько "отводков" кактуса он сможет отдать знакомым своих знакомых. Заметим, что Борис не может отдать кактус тем, кого он не знает.

Формат входного файла input.txt

Первая строка - целые числа N (1 <= N <= 4000) и K (0 <= K <= min(20, N)) - количество сотрудников, работающих в офис-центре (включая Бориса) и количество человек в цепочках знакомых Бориса, которых он уже обеспечил кактусами. Следующие N строк описывают взаимосвязи между сотрудниками офис-центра.

В строке #S+1 сначала указано число знакомых человека #S, а затем перечислены их номера. Если человек #J знаком с человеком #I, то и человек #I считается знакомым человека #J, даже если это не указано явно.

Борис имеет #1. Гарантируется, что ни один человек не является знакомым себя самого.

Формат выходного файла output.txt

Первая строка - количество знакомых знакомых Бориса в офис-центре, которые еще не обзавелись кактусами от Бориса, и через пробел - количество людей, с которыми Борис может познакомиться (с целью отдать кактус)

Пример входного файла

14 3
2 2 6
4 1 3 9 12
2 2 4
3 5 11 7
3 14 4 11
1 8
2 12 11
3 4 9 2
2 4 8
0
1 13
1 2
1 11
1 5

Пример выходного файла

4 1

Сдать задачу

Задать вопрос жюри по этой задаче