e-olymp
Yarışlar

ADA Classes - Graph Applications

Кружки в Маховниках

Маленький Петя очень любит компьютеры и хочет научиться программировать. В небольшом городке Маховники, где он живёт, работает сеть кружков по программированию самой разной тематики. Когда Петя пошел записываться, он увидел большой список, состоящий из n кружков. Петя хочет быть всесторонне развитой личностью, поэтому он собрался отучиться во всех этих кружках. Но когда он собрался записаться на все занятия сразу, обнаружилось, что не всё так просто. Вопервых, в один момент времени разрешается учиться только в одном из этих n кружков. Во-вторых, некоторые преподаватели выдвигают входные требования к знаниям учеников, заключающиеся в знании курсов каких-то других кружков!

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

Перед тем как сесть составлять порядок посещения кружков, Петя внимательно перечитал условия обучения и обнаружил ещё один важный пункт. Оказывается, для привлечения школьников, во всех кружках действует система поощрения учеников конфетами. Это означает, что по окончании очередного кружка ученику выдают несколько коробок конфет, всё больше и больше с каждым пройденным кружком. С другой стороны, в каждом кружке количество конфет в коробке своё, зависящее от сложности курса. Более конкретно - за прохождение i-го по счёту кружка, если этот кружок идёт в общем списке под номером j, ученику выдают аж ni-1 * j конфет - такие щедрые люди программисты. Петя решил совместить полезное с приятным - теперь он хочет выбрать такой порядок посещения кружков, чтобы при этом получить как можно больше конфет, однако эта задача ему уже не под силу. Помогите будущему великому человеку отыскать такой порядок.

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

В первой строке содержится целое число n (1n100 000) - количество кружков в Маховниках. В последующих n строках идут описания входных требований кружков, в порядке их следования в общем списке. В i-ой строке сначала записано целое число ki (0 ≤ kin - 1) - количество кружков, в которых нужно отучиться перед записью в i-й кружок, а потом ki номеров этих кружков. Сумма ki не превосходит 200 000. Гарантируется, что возможно посетить все эти кружки в некотором порядке, не нарушая условия посещения.

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

Выведите n номеров, разделённых пробелами - порядок, в котором Пете надо посещать кружки, чтобы съесть как можно больше конфет.

Пояснение к примеру

Посещая кружки в указанном порядке, Петя получит 60 * 2 + 61 * 1 + 62 * 3 + 63 * 5 + 64 * 4 + 65 * 6 = 2 + 6 + 108 + 1080 + 5184 + 46656 = 53036 конфет.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
6
1 2
0
1 2
3 1 2 5
1 2
4 1 3 4 5
Çıxış verilənləri #1
2 1 3 5 4 6
Mənbə 2013 Московская городская олимпиада по информатике для 6-9 классов, Москва, 3 февраля, Задача E