В Берляндии находятся \(n\) городов. Город с номером \(1\) является столицей. Некоторые пары городов соединены односторонней дорогой длины 1.
Перед поездкой Поликарп для каждого города узнал величину \(d_i\) — расстояние от столицы (города с номером \(1\)) до города с номером \(i\). Поликарп начинает своё путешествие в городе с номером \(s\) и, находясь в \(i\)-м городе, выбирает одно из следующих действий:
- Поехать из \(i\)-го города в \(j\)-й, если существует дорога из \(i\)-го города в \(j\)-й и \(d_i < d_j\);
- Поехать из \(i\)-го города в \(j\)-й, если существует дорога из \(i\)-го города в \(j\)-й и \(d_i \geq d_j\);
- Прекратить путешествие.
Так как правительство Берляндии не хочет, чтобы все люди съезжались в столицу, поэтому Поликарп может не более одного раза совершить действие из пункта два. Иными словами, второе действие он может совершить \(0\) или \(1\) раз. Поликарп же, наоборот, хочет оказаться как можно ближе к столице.
Например, если \(n = 6\) и города соединены, как на картинке выше, то Поликарп мог совершить следующие путешествия (не все возможные варианты):
- \(2 \rightarrow 5 \rightarrow 1 \rightarrow 2 \rightarrow 5\);
- \(3 \rightarrow 6 \rightarrow 2\);
- \(1 \rightarrow 3 \rightarrow 6 \rightarrow 2 \rightarrow 5\).
Поликарп хочет узнать для каждого стартового города \(i\) узнать, на какое ближайшее расстояние он может подобраться к столице. Более формально: он хочет узнать минимальное значение \(d_j\), такое что Поликарп может добраться из города \(i\) в город \(j\) по выше описанным правилам.
Выходные данные
Для каждого набора входных данных в отдельной строке выведите \(n\) чисел, \(i\)-е из которых равно минимально возможному расстоянию от столицы до города, в котором Поликарп закончил своё путешествие.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
6 7
1 2
1 3
2 5
2 4
5 1
3 6
6 2
2 2
1 2
2 1
6 8
1 2
1 5
2 6
6 1
2 3
3 4
4 2
5 4
|
0 0 1 2 0 1
0 0
0 0 2 1 1 0
|