eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Король

Король

Лимит времени 2 секунды
Лимит использования памяти 256 MiB

В Тридесятом царстве, Тридевятом государстве жил-был король. И было у короля n сыновей. В Тридесятом царстве жили n прекрасных девушек, и король знал, какие девушки нравятся каждому сыну (поскольку сыновья были молодыми и безшабашными, то им могли нравиться несколько девушек одновременно).

Однажды король приказал своему советнику подобрать для каждого сына прекрасную девушку, на которой тот сможет жениться. Советник выполнил приказ и подобрал для каждого сына для женитьбы прекрасную девушку, которая ему нравилась. Разумеется, каждая девушка может выйти замуж только за одного из сыновей.

Посмотрев на список невест, король сказал: "Мне нравится этот список, но я хочу знать для каждого сына список всех девушек, на которых он может жениться. Разумеется, при этом все сыновья также должны иметь возможность жениться на девушках, которые им нравятся".

Эта задача оказалась для советника слишком сложной. Помогите ему избежать казни, решив ее.

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

Первая строка входного файла содержит число n — количество сыновей (1n2000). Следующие n строк содержат списки прекрасных девушек, которые нравятся сыновьям. В начале идет k_i — количество девушек, которые нравятся i-му сыну. Затем идут k_i чисел — номера девушек. Сумма k_i не превышает 200000.

Последняя строка входного файла содержит список, составленный советником — n различных чисел от 1 до n: для каждого сына — номер прекрасной девушки, на которой он может жениться. Гарантируется, что список корректен, то есть каждому сыну нравится выбранная для него девушка.

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

Выходной файл должен содержать n строк. Для каждого сына выведите l_i — количество различных девушек, на которых он может жениться. После этого выведите чисел l_i — номера девушек в произвольном порядке.

Пример

Входные данные #1
4
2 1 2
2 1 2
2 2 3
2 3 4
1 2 3 4
Выходные данные #1
2 1 2
2 1 2
1 3
1 4
Автор Виталий Гольдштейн
Источник Зимняя школа, Харьков 2011, День 9