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