题目描述

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

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

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

1. 令 $S=\{v\}$ 且 $h=0$。
2. 当 $|S|<N$ 时
   1. 对于满足只有一个端点在 $S$ 中的所有边，令 $e$ 为满足条件的边中编号最小的一条。
   2. 将不在 $S$ 中的端点加入 $S$。
   3. 令 $h=10h+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$ 开始的情况下最终的返回值。

3 2
1 2
2 3

12
12
21

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$。

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\sim 6$：$N\le 2000$
• 测试点 $7\sim 10$：$N\le 10^4$
• 测试点 $11\sim 14$：对于所有 $e$ 满足 $a_e+1=b_e$
• 测试点 $15\sim 23$：无附加限制

Problem credits: Benjamin Qi