CF1209F Koala and Notebook

考拉之国有 $m$ 条双向道路连接着 $n$ 座城市。道路按输入顺序编号为 $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$ 和 $y_i$ 的双向道路。 保证任意两座城市之间至多有一条道路直接相连，且任意两座城市之间都可以互相到达。

输出 $n-1$ 个整数，第 $i$ 个整数表示到达第 $i+1$ 座城市时，考拉可能写下的最小数字对 $10^9+7$ 取模的结果。

由 ChatGPT 4.1 翻译