A Graph Problem

题目描述

为了提高她的数学知识，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\pmod{10^9+7}$。

请确定该过程对所有起点的返回值。

输入格式

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

接下来有 $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

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

提示

考虑从 $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$。 请确保输出答案时对 $10^9+7$ 取模。 SCORING: Input 4: $N,M\le 2000$ Inputs 5-6: $N\le 2000$ Inputs 7-10: $N\le 10000$ Inputs 11-14: 对所有 $e$，$a_e+1=b_e$ Inputs 15-23: 无额外限制。 题目来源：Benjamin Qi

标签: USACO|2023|Platinum

来源

USACO|2023|Platinum