Король#1939

Король

2 секунди

256 мегабайтів

Легка

У далекому королівстві жив король, у якого було $n$ синів. У цьому королівстві також було $n$ прекрасних дівчат, і король знав, яких дівчат кожен із його синів вподобав. Оскільки сини були молоді й безтурботні, кожен міг вподобати одразу декількох дівчат.

Одного дня король доручив своєму раднику вибрати відповідну дівчину для кожного сина так, щоб він міг на ній одружитися. Радник виконав завдання: для кожного сина він обрав дівчину, яка йому подобається, і забезпечив, щоб кожна дівчина була вибрана лише для одного сина.

Переглянувши список наречених, король сказав: "Мені подобається цей список, але я хочу знати, для кожного сина — список усіх дівчат, на яких він може одружитися. Звісно, всі сини також повинні мати можливість одружитися з тими дівчатами, які їм подобаються."

Це завдання виявилося дуже складним для радника. Допоможіть йому уникнути страти, розв'язавши його.

Вхідні дані

Перший рядок містить число $n$ — кількість синів ( $1 \leq n \leq 2000$ 1 \leq n \leq 2000). Кожен з наступних $n$ рядків містить список дівчат, які подобаються відповідному сину. $i$ -ий із цих рядків починається з $k_{i}$ k_i — кількості дівчат, які подобаються $i$ -ому сину, далі слідують $k_{i}$ k_i чисел — індекси цих дівчат. Сума всіх $k_{i}$ k_i не перевищує $200000$ .

Останній рядок містить список, складений радником: $n$ різних чисел від $1$ до $n$ , де для кожного сина це номер дівчини, на якій він може одружитися. Гарантується, що список правильний, тобто кожному сину дісталася дівчина, яка йому подобається.

Вихідні дані

Виведіть $n$ рядків. Для кожного сина виведіть $l_{i}$ l_i — кількість різних дівчат, на яких він може одружитися. Далі виведіть $l_{i}$ l_i чисел — індекси цих дівчат у будь-якому порядку.

Приклади

Приклад 1