Дороги
В стране X имеется n городов, помеченных цифрами от 1 до n. Дорожная сеть состоит из n - 1 двунаправленных обычных дорог, каждая из которых соединяет два города и имеет фиксированную длину - натуральное число. Каждая из этих дорог была построена в прошлом в разное время, и дорожная сеть спроектирована таким образом, что существует маршрут между любыми двумя городами, который является либо обычной дорогой, либо проходит через другие города, используя обычные дороги. Поскольку автомобильное движение все время увеличивается, правительство планирует заменить обычные дороги двунаправленными автомагистралями. Кроме того, магистрали между городами будут построены в соответствии со следующими правилами:
Автомагистраль будет построена только между двумя городами, между которыми уже существует прямая дорога. Автомагистраль заменяет обычную дорогу.
Только одна автомагистраль может строиться в один момент времени;
Автомагистрали будут построены в том же порядке, в котором были построены обычные дороги (помните, что все обычные дороги были построены в разное время);
Назовем "районом" страны любое максимальное подмножество городов и обычных дорог (без автомагистралей) начальной дорожной сети, так что между любыми двумя городами в ней есть маршрут с использованием только обычных дорог. После строительства каждой магистрали ровно одна область страны разделяется на две области (возможно, что одна или обе новые зоны состоят из одного города без дорог). "Простой маршрут" - это маршрут, который может проходить через город не чаще одного раза. После строительства каждой новой автомагистрали правительство города X хотело бы узнать длину самых длинных простых маршрутов между двумя городами в каждой из двух новых областей.
Напишите программу, которая ответит на эти вопросы.
Входные данные
Первая строка содержит одно натуральное число n (1 ≤ n ≤ 500000) - количество городов в стране X.
Следующие n - 1 строк описывают существующую сеть дорог перед созданием автомагистралей. Каждая строка содержит три натуральных числа - первые два обозначают номера городов, между которыми имеется обычная дорога, а третья - ее длина.
Обычные дороги задаются в том же порядке, в котором они были построены.
Длины всех обычных дорог находятся между 1 и 1000 включительно.
Выходные данные
Вывести n - 1 строк - в i-ой строке вывести два целых числа, разделенных пробелом – длины наибольших путей (используя только обычные дороги) между двумя городами в каждой из двух новых областей, образованных после построения i-ой автомагистрали. Числа следует выводить в невозрастающем порядке.
Объяснение
Обозначим через {t[1], t[2], ..., t[k]} область, содержащую города t[1], t[2], ..., t[k] и обычные дороги между ними.
1.Перед построением первой автомагистрали:
Существует только одна область {1, 2, 3, 4, 5}.
2.После построения первой автомагистрали между городами 1 и 2:
Страна разбивается на две области - {1, 5} и {2, 3, 4}. Длины наибольших путей между городами в каждой из них: в {1, 5} - 3 (между городами 1 и 5); в {2, 3, 4} - 3 (между городами 3 и 4).
3.После построения второй автомагистрали между городами 2 и 3:
Область {2, 3, 4} разбивается на две - {3} и {2, 4}. Длины наибольших путей между городами в каждой из них 0 и 2. Выводим их в возрастающем порядке!
4.После построения третьей автомагистрали между городами 2 и 4:
Область {2, 4} разбивается на две - {2} и {4}. Длины наибольших путей в обоих областях 0.
5.После построения четвертой автомагистрали между городами 1 и 5:
Область {1, 5} разбивается на {1} и {5}. Длины наибольших путей 0.