問題
수학적 지식을 향상시키기 위해 Bessie는 그래프 이론 과정을 수강하고 다음과 같은 문제에 어려움을 겪고 있습니다. 도와주세요!
라벨이 1에서 N까지인 정점들과 1에서 M까지 라벨이 지정된 연결된 무방향 그래프가 주어집니다 (2≤N≤2⋅105, N−1≤M≤4⋅105). 그래프의 각 정점 v에 대해 다음 프로세스가 수행됩니다:
S={v}이고 h=0인 상태로 시작합니다.
|S|<N일 동안 다음을 반복합니다.
정확히 하나의 끝점이 S에 속하는 모든 간선 중에서 라벨이 가장 작은 간선 e를 선택합니다.
e의 S에 속하지 않은 끝점을 S에 추가합니다.
h=10h+e로 설정합니다.
h(mod109+7)을 반환합니다.
이 프로세스의 모든 반환 값을 결정하세요.
A Graph Problem
To improve her mathematical knowledge, Bessie has been taking a graph theory course and finds herself stumped by the following problem. Please help her!
You are given a connected, undirected graph with vertices labeled 1…N and edges labeled 1…M (2≤N≤2⋅10^5, N−1≤M≤4⋅10^5). For each vertex v
in the graph, the following process is conducted:
1. Let S={v} and h=0.
2. While |S|<N,
1. Out of all edges with exactly one endpoint in S, let e be the edge with the minimum label.
2. Add the endpoint of e not in S to S.
3. Set h=10h+e.
3. Return h(mod109+7).
Determine all the return values of this process.
輸入
첫 번째 줄에는 N과 M이 주어집니다. 그런 다음 M개의 줄이 따릅니다. eth 줄에는 eth 간선의 끝점인 (ae,be)이 주어집니다 (1≤ae<be≤N). 이러한 간선들이 연결된 그래프를 형성하며 각 정점 쌍에 최대 하나의 간선이 연결되어 있다는 것이 보장됩니다.
The first line contains N and M.Then follow M lines, the eth containing the endpoints (ae,be) of the eth edge (1≤ae<be≤N). It is guaranteed that these edges form a connected graph, and at most one edge connects each pair of vertices.
輸出
i번째 줄에는 정점 i에서 시작하는 프로세스의 반환 값을 출력하세요.
Output N lines, where the ith line should contain the return value of the process starting at vertex 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입니다.
Consider starting at i=3. First, we choose edge 2, after which S={3,4} and h=2. Second, we choose edge 3, after which S={2,3,4} and h=23. Third, we choose edge 1, after which S={1,2,3,4} and h=231. Finally, we choose edge 5, after which S={1,2,3,4,5} and h=2315. The answer for i=3 is therefore 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.로 나눈 값을 출력하세요.
Make sure to output the answers modulo 10^9+7.
需要登入才能撰寫程式碼。