06724. USACO·最小生成树序列 未做

为了提高自己的数学水平，Bessie 正在修一门图论课程，却被下面这道题难住了。请帮帮她！

给定一张连通的无向图，顶点标号为 $1\dots N$，边标号为 $1\dots M$（$2\le N\le 2\cdot 10^5$，$N-1\le M\le 4\cdot 10^5$）。对图中的每个顶点 $v$，都会进行如下过程：

• 令 $S=\{v\}$，$h=0$。
• 当 $|S|<N$ 时：
  • 在所有恰有一个端点属于 $S$ 的边中，令 $e$ 为标号最小的边。
  • 将 $e$ 中不属于 $S$ 的那个端点加入 $S$。
  • 令 $h=10h+e$。
• 返回 $h(\mathrm{mod}10^9+7)$。

求出该过程的所有返回值。

第一行包含 $N$ 和 $M$。

接下来 $M$ 行，第 $e$ 行包含第 $e$ 条边的端点 $(a_e,b_e)$（$1\le a_e<b_e\le N$）。保证这些边构成一张连通图，且每对顶点之间至多有一条边。

输出 $N$ 行，第 $i$ 行应包含从顶点 $i$ 出发时该过程的返回值。

【样例解释】

务必输出对 $10^9+7$ 取模后的答案。

【数据规模与约定】

• 测试点 4：$N,M\le 2000$

• 测试点 5-6：$N\le 2000$

• 测试点 7-10：$N\le 10000$

• 测试点 11-14：对所有 $e$ 有 $a_e+1=b_e$

• 测试点 15-23：无附加限制。