Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки

HotLog


 

Диверсия

(Время: 5 сек. Память: 16 Мб Сложность: 70%)

В королевстве Далеком n городов, соединенных m двусторонними дорогами. Некоторые дороги вымощены камнем, а другие представляют собой лишь обычные проселочные дороги. Столица королевства расположена в городе номер 1. Дороги устроены таким образом, что можно из любого города добраться до любого другого, перемещаясь исключительно по вымощенным камнем дорогам, причем количество каменных дорог минимальное возможное. Проселочные же дороги были построены таким образом, что если каменная дорога заблокирована или уничтожена, то все равно можно добраться из любого города до любого другого по дорогам.

Обозначим количество каменных дорог, по которым требуется проехать, чтобы попасть из города u в город v как s(u, v). Дороги подчиняются следующему правилу: если два города u и v соединены дорогой (неважно, каменной или проселочной), то либо s(1, u) + s(u, v) = s(1, v), либо s(1, v) + s(v, u) = s(1, u).

Король соседнего королевства планирует напасть на Далекое. В качестве начала операции предполагается уничтожить некоторые дороги. Расчеты показали, что финансирования, выделенного министерству атаки, достаточно, чтобы уничтожить ровно одну каменную и одну проселочную дорогу. Король хотел бы уничтожить такую пару дорог, чтобы после этого хотя бы для каких-нибудь двух городов стало невозможно добраться из одного города в другой.

Теперь он просит министра атаки посчитать количество возможных диверсионных планов. Однако министр атаки обучен только атаковать, считать для него слишком сложно. Помогите ему!

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

Первая строка входного файла INPUT.TXT содержит n и m – количество городов и дорог, соответственно (3 ≤ n ≤ 20 000, m ≤ 100 000). Следующие m строк описывают дороги, каждая строка содержит три целых числа – номера городов, соединенных соответствующей дорогой, и 1, если соответствующая дорога вымощена камнем, или 0, если соответствующая дорога – проселочная. Никакие два города не соединены более чем одной дорогой, никакая дорога не соединяет город сам с собой.

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

В выходной файл OUTPUT.TXT выведите одно целое число – количество способов организовать диверсию.

Пример

INPUT.TXTOUTPUT.TXT
16 7
1 2 1
2 3 1
1 4 0
3 4 1
4 5 1
3 6 0
5 6 1
4

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2021, E-mail: admin@acmp.ru