Олимпиадный тренинг

Задача . F. Коала и блокнот


Задача

Темы: Строки Деревья Структуры данных *2600 поиск в глубину и подобное графы кратчайшие пути

Страна коал состоит из \(n\) городов и \(m\) двусторонних дорог, их соединяющих. Дороги пронумерованы от \(1\) до \(m\) в порядке входных данных. Гарантируется, что можно добраться от каждого города до любого другого города.

Коала начинает путешествие из города \(1\). Каждый раз, когда он проходит по дороге, он записывает её номер в блокнот. Он не делает пробелов между числами, так что все записи склеятся в одно большое число.

Перед тем как отправится в свой путь, Коала интересуется какое число может получится в блокноте в зависимости от конечного пункта. Для каждого возможного конечного пункта выясните, какое наименьшее число может для него получиться?

Так как эти числа могут быть достаточно большими, вычислите их по модулю \(10^9+7\). Обратите внимание, что нужно вычислить остаток минимального возможного числа, не минимально возможный остаток.

Входные данные

Первая строка содержит два целых числа \(n\) и \(m\) (\(2 \le n \le 10^5, n - 1 \le m \le 10^5\)) — количество городов и количество дорог соответственно.

\(i\)-я из следующих \(m\) строк содержит целые числа \(x_i\) и \(y_i\) (\(1 \le x_i, y_i \le n\), \(x_i \ne y_i\)), обозначающие двустороннюю дорогу между \(x_i\) и \(y_i\).

Гарантируется, что для каждой пары городов есть не более одной дороги их соединяющей, и что можно добраться из каждого города до любого другого.

Выходные данные

Выведите \(n - 1\) целое число — ответ для каждого города за исключением первого.

\(i\)-е число должно быть равно наименьшему числу, которое получилось бы для конечной точки \(i+1\). Так как это число может быть достаточно большим, выведите его остаток по модулю \(10^9+7\).


Примеры
№Входные данныеВыходные данные
1 
11 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
 
1
12
123
1234
12345
123456
1234567
12345678
123456789
345678826
2 
12 19
1 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
3 11
11 12
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
 
1
12
13
14
15
16
17
18
19
1210
121011
3 
12 14
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
1 3
1 4
1 10
 
1
12
13
134
1345
13456
1498
149
14
1410
141011

time 2000 ms
memory 512 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++5
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет