Дан связный неориентированный взвешенный граф с n вершинами и m ребрами. Граф не содержит петель и мультиребер. Рассмотрим некоторое ребро с номером i. Для него определим наибольший возможный вес, который можно присвоить этому ребру, чтобы оно содержалось во всех минимальный покрывающих деревьях данного графа.
Требуется для каждого ребра посчитать максимальный вес по описанным правилам. При этом для каждого ребра ответ должен считаться независимо, то есть в графе может существовать максимум одно ребро с измененным весом.
Выходные данные
В единственной строке выведите через пробел искомые веса ребер в том порядке, в котором они заданы во входных данных. Если ребро при любом весе будет содержаться во всех покрывающих деревьях, выведите для него -1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 4
1 2 2
2 3 2
3 4 2
4 1 3
|
2 2 2 1
|
|
2
|
4 3
1 2 2
2 3 2
3 4 2
|
-1 -1 -1
|