Задача На дне (BOTTOM)
На дне некоторого озера
находятся N
домиков, в каждом из которых живет по одной черепахе. В гости к ним собирается
дружелюбный Краб, который хотел бы поселиться у такой черепахи, живя у которой
он бы мог посетить максимальное количество других. Для перемещения между
домиками существуют трассы с односторонним движением, которые соединяют два
домика, по которым краб может перемещаться нормально и задом наперед. По трассе
с движением из A в B краб может перемещаться из A в B, если он перемещается нормально и из B в A, если он перемещается задом наперед.
Из домика, где поселится Краб,
он начинает движение задом наперед. Однако среди всех подводных трасс есть
такие, после движения по которым Краб всегда меняет способ своего движения на
противоположный. В никаком другом месте кроме этих специальных трасс он не
может менять свой способ перемещения.
Посетить другую черепаху Краб
может только в том случае, если выходя из домика где он поселился, он может,
согласно своим правилам движения, дойти до нужной черепахи и после этого
вернуться к той, которая его приютила, причем вернуться так, чтобы по окончанию
путешествия направление Краба было опять задом наперед.
Помогите Крабу определить, к
какой из черепах ему лучше поселиться, чтобы посетить максимальное количество
других подводных обитательниц. А для этого, поскольку Краб недоверчив,
подсчитайте для каждого из подводных жилищ количество черепах, которых может
посетить Краб, проживая в данном. Причем, очевидно, что черепаху, у которой он
живет, посещать не нужно.
Формат ввода/вывода:
Напишите
программу BOTTOM, которая читает входные данные из
файла BOTTOM.DAT и записывает ответ в файл BOTTOM.SOL.
В первой строке файла BOTTOM.DAT находятся два целых числа 
и 
– количество домиков и количество трасс
соответственно. В следующих строках находятся описания трасс, по одному в
каждой строке. Описание трасс состоит из трёх чисел 
,
где 
а 
равно 
или 
.
Число 
a это номер дома, в котором трасса начинается, 
– это номер дома, где заканчивается трасса. Если
,
то трасса обычная, а если 
,
то трасса специального типа.
Файл
BOTTOM.SOL
должен содержать ровно строк, в 
-ой строке должно быть число друзей
которых он сможет посетить живя в доме номер .
Ограничения: 
, 
.
Пример:
|
BOTTOM.DAT 5 5 2 1 1 2 3 0 3 4 0 4 2 0 5 3 1 |
BOTTOM.SOL 3 3 3 3 0 |
Живя в доме 1, Краб может посетить приятелей в домах 2,
3, 4. Живя в доме 2, Краб может посетить приятелей в домах 3, 4, 5. Живя в доме
3, Краб может посетить приятелей в домах 2, 4, 5. Живя в доме 4, Краб может посетить приятелей
в домах 2, 3, 5. Живя в доме 5, Краб не может посетить никого.