题目详情题解（0）讨论（0）提交记录（0）

A90537.「USACO 2023.12 Platinum」A Graph Problem

省选/NOI-

通过率：0%

时间限制：2.00s

内存限制：256MB

题目描述

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

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

给定一个无向连通图，点编号为 11 到 NN，边编号为 11 到 MM。对于图中的每个点 vv 进行如下操作：

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

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

输入格式

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

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

输出格式

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

输入输出样例

  • 输入#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

说明/提示

  • 测试点 44：N,M≤2000N,M\le 2000
  • 测试点 5∼65\sim 6：N≤2000N\le 2000
  • 测试点 7∼107\sim 10：N≤104N\le 10^4
  • 测试点 11∼1411\sim 14：对于所有 ee 满足 ae+1=bea_e+1=b_e
  • 测试点 15∼2315\sim 23：无附加限制

Problem credits: Benjamin Qi

首页