В Байтландии собираются провести ярмарку. В Байтландии \(n\) городов, которые соединены \(m\) двухсторонними дорогами, причём из любого города можно доехать до любого другого, передвигаясь только по дорогам.
В Байтландии производят \(k\) различных товаров, причём каждый город специализируется на одном товаре. Чтобы ярмарка состоялась, на неё нужно привезти хотя бы \(s\) различных товаров. Чтобы привезти товары из города \(u\) в город \(v\) нужно потратить \(d(u,v)\) монет, где \(d(u,v)\) — длина кратчайшего пути между городами \(u\) и \(v\). Длина пути — это количество дорог, которые входят в этот путь.
Организаторы ярмарки оплатят перевозку товаров, однако они сами могут выбрать, производителей из каких городов пригласить на ярмарку. Теперь организаторы хотят для каждого из \(n\) городов посчитать, какое минимальное количество монет нужно потратить на перевозку товаров, чтобы провести ярмарку в этом городе.
Выходные данные
Выведите \(n\) чисел, \(i\)-е из которых — минимальное количество монет на перевозку товаров при проведении ярмарки в городе \(i\). Разделяйте числа пробелами.
Примечание
Рассмотрим первый пример.
Чтобы провести ярмарку в городе \(1\), можно привезти товары из городов \(1\) (\(0\) монет), \(2\) (\(1\) монета) и \(4\) (\(1\) монета). Суммарное количество монет равно \(2\).
Город \(2\): Товары из городов \(2\) (\(0\)), \(1\) (\(1\)), \(3\) (\(1\)). Сумма \(2\).
Город \(3\): Товары из городов \(3\) (\(0\)), \(2\) (\(1\)), \(4\) (\(1\)). Сумма \(2\).
Город \(4\): Товары из городов \(4\) (\(0\)), \(1\) (\(1\)), \(5\) (\(1\)). Сумма \(2\).
Город \(5\): Товары из городов \(5\) (\(0\)), \(4\) (\(1\)), \(3\) (\(2\)). Сумма \(3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 5 4 3
1 2 4 3 2
1 2
2 3
3 4
4 1
4 5
|
2 2 2 2 3
|
|
2
|
7 6 3 2
1 2 3 3 2 2 1
1 2
2 3
3 4
2 5
5 6
6 7
|
1 1 1 2 2 1 1
|