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