Задача C. Марфа Геннадьевна и социальная сеть ≡

Условие

Однажды в деревне, где живёт Марфа Геннадьевна, была организована компьютерная сеть, которую соорудил местный системный администратор-самоучка Никифор Петрович. Он же настроил все имеющиеся в деревне компьютеры, организовал передачу данных по проводам, а также через Wi-Fi.

Деревенский программист-самоучка Иван Никанорович создал социальную сеть ДN ("Деревня Network") специально для жителей деревень, и деревенские жители стали регистрироваться в этой социальной сети.

Как и в остальных социальных сетях, в социальной сети ДN у каждого пользователя есть так называемый "список друзей", и пользователи могут отправлять друг другу сообщения.

Как-то раз Марфа Геннадьевна нашла в интернете интересный сайт с хорошими кулинарными рецептами и решила сообщить об этом сайте другим деревенским жителям.

Однажды утром Марфа Геннадьевна отправила всем пользователям сети ДN из "списка её друзей" ссылку на интересный сайт. Вечером все эти пользователи получили сообщение.

Затем информация распространялась по сети ДN следующим образом.

1. Сообщения отправляются только утром, а получаются только вечером.
2. Если пользователь B получил информацию от пользователя A, то утром следующего дня пользователь B разошлёт эту информацию всем пользователям из "списка его друзей", от которых он не получал эту информацию и которым он не отправлял эту информацию.

Отметим, что социальная сеть ДN устроена таким образом, что если пользователь B находится в "списке друзей" пользователя A, то и пользователь A находится в "списке друзей" пользователя B. Никакой пользователь не может находиться в своём же "списке друзей".

Требуется определить, сколько раз каждый пользователь социальной сети ДN получит информацию (ссылку на сайт с кулинарными рецептами).

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

Первая строка входного файла содержит целое число N — количество пользователей социальной сети ДN.

Далее для каждого пользователя во входном файле записана следующая информация. Сначала идёт целое число k_i — количество пользователей в "списке друзей" пользователя i, за которым следуют k_i различных целых чисел от 1 до N — номера пользователей из списка друзей i-го пользователя.

Марфа Геннадьевна — это пользователь с номером 1.

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

Требуется вывести в выходной файл N целых чисел: для каждого пользователя социальной сети ДN нужно вывести, сколько раз он получит ссылку на сайт.

Ограничения

1 ≤ N ≤ 100.

0 ≤ k_i < N.

Примеры тестов

3
2  2 3
1  1
1  1

0 1 1

3
2  2 3
2  3 1
2  1 2

0 2 2

6
1  2
3  1 3 4
2  5 2
2  2 5
2  4 3
0

0 1 1 1 2 0

Разбор

Скачать файл с разбором