Задача H. Желания
Задачу добавил: alef
Успешно сдано решений: 12
Хасан долго раскладывал камни, но ему так и не удавалось добиться равной суммарной магической силы кругов. Сколько он ни старался, но каждый раз получалась небольшая разница... Он продолжал перекладывать камни, и не заметил, как к нему подошел Мурад. Мурад посмотрел на то, как были разложены камни, снял один небольшой камень со второго круга, и книга тотчас стала излучать мягкий неяркий свет.- А это - твоя награда, - сказал Мурад, держа в ладони рубин, - подумай хорошенько, какое свое желание ты больше всего хотел бы видеть исполненным. И назавтра это произойдет.
Хасан был рад, и вместе с тем несколько растерян. Много было разных желаний у него, но выбрать надо было одно. Более того, Хасан понял, что некоторые его желания несовместимы. Например, он хотел бы много путешествовать, но при том ему нравилось ремесло ювелира. А если обзавестись своей мастерской, то путешествовать много вряд ли получится.
Поэтому Хасан решил найти то желание, которое совместимо с как можно большим количеством других.
Для этого он взял лист бумаги и перо, и стал записывать свои желания, каждое на отдельной строке. Затем он рядом с каждым желанием записал номера тех, которые с ним очевидно несовместимы.
Понятно, что если желание "А" несовместимо с желанием "B", то обратное также верно - желание "В" несовместимо с желанием "А". Однако желание "А" может быть одновременно совместимо с желаниями "В" и "С", хотя желания "В" и "С" несовместимы друг с другом.
Затем Хасан заметил, что исполнение некоторых желаний может положительно повлиять на исполнение других. Например, его желание много путешествовать может помочь исполнению его желания много знать о разных странах. Обратное, вообще говоря, неверно - о разных странах можно много узнать, например, читая книги. Тогда он составил второй список - рядом с каждым желанием записал номера тех, на исполнение которых оно может положительно повлиять.
Разумеется, если желание "A" положительно влияет на исполнение желания "B" а желание "B" положительно влияет на исполнение желания "C", то можно говорить, что желание "A" положительно влияет на исполнение желания "C".
Конечно, есть желания, исполнение которых никак не связано между собой.
Теперь Хасан хочет посчитать для каждого желания его "общий рейтинг".
Назовем желания, на которые положительно влияет данное желание, "исполнимыми" (разумеется, желание положительно влияет на само себя).
Будем считать, что все желания, которые не являются "исполнимыми" (с точки зрения данного желания) и на которые положительно влияет какое-либо желание, не совместимое с данным, "неисполнимыми".
"Общим рейтингом" будем называть разницу между числом "исполнимых" и "неисполнимых" желаний
Хасан спешил и волновался, и поэтому мог ошибиться. Поэтому, если какое-либо желание оказалось "исполнимым" с точки зрения данного, и "неисполнимым" (прямо или косвенно), то будем полагать, что он напрасно считал это желание "неисполнимым" и не будем учитывать его как "неисполнимое" при подсчете общего рейтинга.
Ваша задача - помочь Хасану посчитать общие рейтинги всех желаний.
Формат входного файла input.txt
Первая строка - целое число N (1 <= N <= 1000) - количество желаний, которое есть у Хасана
В следующих N строках содержится информация о несовместимости желаний.
Так, в строке #k (k = 2, 3, ..., N+1) через пробел содержатся целые числа - номера желаний, несовместимых с желанием #(k-1). Если желание #p несовместимо с желанием #q, то и желание #q несовместимо с желанием #p, даже если для желания #q это явно не указано. Каждая из этих строк заканчивается нулем.
В следующих N строках содержится информация о положительном влиянии одних желаний на исполнение других желаний.
Так, в строке #m (m = N+2, N+3, ... N+N+1) через пробел содержатся целые числа - номера желаний, на которые исполнение желания #(m-N-1) повлияет положительно. Если желание #m положительно влияет на исполнение желания #k, а желание #k положительно влияет на исполнение желания #s, то желание #m положительно влияет на исполнение желания #s, даже если для желания #m это явно не указано. Каждая из этих N строк также заканчивается нулем.
Формат выходного файла output.txt
Первая строка - N целых числа Rj через пробел. (j = 1, 2, ..., N - номера желаний), Rj - общий рейтинг желания #j.
Пример входного файла
5
4 0
5 1 0
5 4 0
3 1 0
1 0
4 3 0
5 1 0
2 0
5 0
3 2 0
Пример выходного файла
5 5 5 5 5