Chouti устал от утомительного домашнего задания и решил открыть старую задачу, которую он придумал несколько лет назад.
Дан связный неориентированный граф, состоящий из \(n\) вершин и \(m\) взвешенных ребер. Также есть \(k\) выделенных вершин: \(x_1, x_2, \ldots, x_k\).
Определим стоимость пути как максимальный вес среди рёбер на пути, а расстояние между двумя вершинами как минимальную стоимость пути, их соединяющего.
Для каждой выделенной вершины найдите другую выделенную вершину, которая является максимально далёкой от неё (в терминах абзаца выше, то есть соответствующее расстояние максимально возможное), и выведите расстояние между ними.
Оригинальные ограничения очень маленькие, поэтому он подумал, что задача скучная. Теперь он увеличил ограничения и надеется, что вы можете решить эту задачу за него.
Выходные данные
В единственной строке выведите \(k\) целых чисел, где \(i\)-е из них должно равняться расстоянию между вершиной \(x_i\) и самой далёкой от неё выделенной вершиной.
Примечание
В первом примере, расстояние между вершинами \(1\) и \(2\) равно \(2\), потому что можно пройти по ребру веса \(2\), соединяющему их. Поэтому, расстояние до самой далекой точки от обеих вершин \(1\) и \(2\) равно \(2\).
Во втором примере, расстояние между вершинами \(1\) и \(2\) и расстояние между вершинами \(1\) и \(3\) равны \(3\), а расстояние между вершинами \(2\) и \(3\) равно \(2\).
В графе могут содержаться параллельные ребра и петли, как в первом примере.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 3 2
2 1
1 2 3
1 2 2
2 2 1
|
2 2
|
|
2
|
4 5 3
1 2 3
1 2 5
4 2 1
2 3 2
1 4 4
1 3 3
|
3 3 3
|