题目描述

题目译自 USACO 2023 December Contest, Platinum Problem 2. A Graph Problem

为了提高自己的数学知识，$Bessie$ 一直在学习图论课程，她发现自己被下面的问题难住了。请帮帮她！

给定一个无向连通图，点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。对于图中的每个点 $v$ 进行如下操作：

1. 令 $S = \{v\}$ 且 $h = 0$。
2. 当 $|S| < N$ 时：
   • 对于满足只有一个端点在 $S$ 中的所有边，令 $e$ 为满足条件的边中编号最小的一条。
   • 将不在 $S$ 中的端点加入 $S$。
   • 令 $h = 10 \cdot h + e$。
3. 返回 $h \pmod{10^9+7}$。

确定这个过程的所有返回值。

---

输入格式

第一行包含两个整数 $N$ $(2 \le N \le 2 \cdot 10^5)$ 和 $M$ $(N-1 \le M \le 4 \cdot 10^5)$。

接下来 $M$ 行，第 $e$ 行包含第 $e$ 条边的两个端点 $(a_e, b_e)$ $(1 \le a_e < b_e \le N)$。保证这些边构成一张连通图，并且每对顶点最多由一条边相连。

---

输出格式

输出 $N$ 行，第 $i$ 行表示操作从点 $i$ 开始的情况下最终的返回值。

---

样例 1

输入

3 2
1 2
2 3

输出

12
12
21

---

样例 2

输入

5 6
1 2
3 4
2 4
2 3
2 5
1 5

输出

1325
1325
2315
2315
5132

考虑从 $i=3$ 开始。首先，我们选择边 $2$，之后 $S=\{3,4\}$，$h=2$。然后，我们选择边 $3$，之后 $S=\{2,3,4\}$，$h=23$。接着，我们选择边 $1$，之后 $S=\{1,2,3,4\}$，$h=231$。最后，我们选择边 $5$，之后 $S=\{1,2,3,4,5\}$，$h=2315$。所以 $i=3$ 的答案为 $2315$。

---

样例 3

输入

15 14
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15

输出

678925929
678925929
678862929
678787329
678709839
678632097
178554320
218476543
321398766
431520989
542453212
653475435
764507558
875540761
986574081

注意输出对 $10^9+7$ 取模。

---

数据范围与提示

• 测试点 4：$N, M \le 2000$
• 测试点 5~6：$N \le 2000$
• 测试点 7~10：$N \le 10^4$
• 测试点 11~14：对于所有 $e$ 满足 $a_e + 1 = b_e$
• 测试点 15~23：无附加限制