← 返回题目列表

Codeforces · 1209/F

F. 考拉和笔记本

中文机器翻译题面 查看原题

Koala Land 由连接 $$$n$$$ 个城市的 $$$m$$$ 双向道路组成。道路按输入顺序从 $$$1$$$ 到 $$$m$$$ 编号。可以保证,人们可以从所有其他城市到达任何一个城市。

考拉从 $$$1$$$ 城市开始旅行。每当他在路上行驶时,他都会在笔记本上记下该路的号码。他没有在数字之间添加空格,因此它们全部连接成一个数字。

在开始旅行之前,考拉很好奇所有可能目的地的最终数字。对于每个可能的目的地,他可以写的最小数字是多少?

由于这些数字可能非常大,因此打印它们对 $$$10^9+7$$$ 取模后的余数。请注意,您需要计算最小可能数的余数,而不是最小可能余数。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 10^5, n - 1 \le m \le 10^5$$$),分别表示城市数量和道路数量。

以下 $$$m$$$ 行中的第 $$$i$$$ 行包含整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$, $$$x_i \ne y_i$$$),表示城市 $$$x_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

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

输出 #2

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

输出 #3

1
12
13
134
1345
13456
1498
149
14
1410
141011