После успешных полевых испытаний, Хайди хочет развернуть ловушку вдоль какого-нибудь Коридора, не обязательно первого. Она хочет избежать встречи с Далеками внутри Временного Вихря, поэтому для большей осторожности она рассматривает размещение ловушек только вдоль тех коридоров, которые не будут использоваться в соответствии с текущим планом Далеков, который представляет из себя минимальное остовное дерево из Коридоров. Хайди знает, что потребности в энергии для всех Коридоров теперь разные, и что у Далеков есть единственный план, который они собираются использовать.
Вашей задачей является вычисление функции $$$E_{max}(c)$$$, которая определена также как и в лёгкой версии — как наибольшее $$$e \le 10^9$$$, такое что если мы изменим энергию коридора $$$c$$$ на $$$e$$$, то Далеки могут им воспользоваться. Однако теперь эту функцию нужно вычислить для каждого коридора, который Хайди рассматривает.
Первая строка содержит целые числа $$$n$$$ и $$$m$$$ ($$$2 \leq n \leq 10^5$$$, $$$n - 1 \leq m \leq 10^6$$$) — количество точек и количество Временных Коридоров.
Каждая из следующих $$$m$$$ строк содержит номера точек $$$a$$$ и $$$b$$$ и требуемой энергии $$$e$$$ ($$$1 \leq a, b \leq n$$$, $$$a \neq b$$$, $$$0 \leq e \leq 10^9$$$).
Ни одна пара $$$\{a, b\}$$$ не повторяется. Гарантируется, что граф является связным. Все требования на уровни энергии $$$e$$$ являются различными.
Выведите $$$m-(n-1)$$$ строк по одному целому числу в каждой: $$$E_{max}(c_i)$$$ для $$$i$$$-го Коридора $$$c_i$$$ из входных данных, среди тех, которые не входят в План Далеков (минимальное остовное дерево)
3 3
1 2 8
2 3 3
3 1 4
4
Если $$$m = n-1$$$, то вам следует ничего не выводить.
Название |
---|