[USACO23DEC] A Graph Problem P
题目描述
为了丰富自己的数学知识,Bessie 选修了一门图论课程,她发现她被下面的问题困住了,请帮帮她!
给出一张连通的无向图,包含编号为 $1\dots N$ 的节点和编号为 $1\dots M$($2 \le N \le 2\cdot 10^5$,$N - 1 \le M \le 4 \cdot 10^5$)的边,下边的操作将被实施:
1. 假设集合 $S=\{v\}$,变量 $h=0$。
2. 当 $|S|<N$,重复执行:
1. 仅有一个顶点在集合 $S$ 中的边中,找到编号最小的那条,编号记为 $e$。
2. 将 $e$ 不在 $S$ 中的那个顶点加入集合 $S$。
3. 将 $h$ 修改为 $10h+e$。
3. 返回 $h$ 对 $10^9+7$ 取模的值。
输出这个过程的全部返回值。
输入输出格式
输入格式
第一行包含 $N$ 和 $M$。接下来 $M$ 行,每行包含第 $e$ 条边的顶点 $(a_e,b_e)$,保证图连通,没有重边。
输出格式
输出 $N$ 行,第 $i$ 行包含在节点 $i$ 开始过程的返回值。
输入输出样例
输入样例 #1
3 2
1 2
2 3
输出样例 #1
12
12
21
输入样例 #2
5 6
1 2
3 4
2 4
2 3
2 5
1 5
输出样例 #2
1325
1325
2315
2315
5132
输入样例 #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
输出样例 #3
678925929
678925929
678862929
678787329
678709839
678632097
178554320
218476543
321398766
431520989
542453212
653475435
764507558
875540761
986574081
说明
### 样例解释 2
考虑在 $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
确保答案对 $10^9+7$ 取模。
### 测试点性质
- 测试点 $4$ 满足 $N,M \le 2000$。
- 测试点 $5-6$ 满足 $N \le 2000$。
- 测试点 $7-10$ 满足 $N \le 10000$。
- 测试点 $11-14$ 满足对于所有边,有 $a_e+1=b_e$。
- 测试点 $15-23$ 没有额外限制。