CF1209F.Koala and Notebook

Koala Land consists of $m$ bidirectional roads connecting $n$ cities. The roads are numbered from $1$ to $m$ by order in input. It is guaranteed, that one can reach any city from every other city.

Koala starts traveling from city $1$. Whenever he travels on a road, he writes its number down in his notebook. He doesn't put spaces between the numbers, so they all get concatenated into a single number.

Before embarking on his trip, Koala is curious about the resulting number for all possible destinations. For each possible destination, what is the smallest number he could have written for it?

Since these numbers may be quite large, print their remainders modulo $10^9+7$. Please note, that you need to compute the remainder of the minimum possible number, not the minimum possible remainder.

考拉国由 $m$ 条双向道路连接 $n$ 座城市。这些道路按输入顺序编号为 $1$ 到 $m$。保证任意两座城市之间均可互相到达。

考拉从第 $1$ 号城市出发。每当他经过一条道路时，就会将该道路的编号记录在笔记本上。他不会在数字之间添加空格，因此所有数字会直接拼接成一个单一的整数。

在启程之前，考拉好奇：对于每一个可能的目的地，他所能写出的这个拼接整数的最小值是多少？

由于这些数字可能非常大，请输出它们对 $10^9+7$ 取模的结果。请注意：你需要先求出最小可能的整数，再对该整数取模，而不是对所有可能结果取模后再取最小值。

The first line contains two integers $n$ and $m$ ($2 \le n \le 10^5, n - 1 \le m \le 10^5$), the number of cities and the number of roads, respectively.

The $i$-th of the following $m$ lines contains integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n$, $x_i \ne y_i$), representing a bidirectional road between cities $x_i$ and $y_i$.

It is guaranteed, that for any pair of cities there is at most one road connecting them, and that one can reach any city from every other city.

第一行包含两个整数 $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$ 与城市 $y_i$ 之间有一条双向道路。

保证任意两座城市之间至多只有一条道路相连，且任意一座城市均可通过道路到达其他任意一座城市。

Print $n - 1$ integers, the answer for every city except for the first city.

The $i$-th integer should be equal to the smallest number he could have written for destination $i+1$. Since this number may be large, output its remainder modulo $10^9+7$.

输出 $n - 1$ 个整数，分别表示除第一个城市外其余每个城市的答案。

第 $i$ 个整数应等于他为目的地 $i+1$ 所能写出的最小数字。由于该数字可能很大，请输出其对 $10^9+7$ 取模的结果。