A Graph Problem | Code Joint

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 \dots N$ and edges labeled $1 \dots M$ ( $2 \leq N \leq 2 \cdot 1 0^{5}$ , $N - 1 \leq M \leq 4 \cdot 1 0^{5}$ ). For each vertex $v$ in the graph, the following process is conducted:

Let $S = {v}$ and $h = 0$ .
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 = 10 h + e$ .
Return $h (mod 1 0^{9} + 7)$ .

Determine all the return values of this process.

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

Make sure to output the answers modulo $1 0^{9} + 7$ .

SCORING:

Input 4: $N, M \leq 2000$
Inputs 5-6: $N \leq 2000$
Inputs 7-10: $N \leq 10000$
Inputs 11-14: $a_{e} + 1 = b_{e}$ for all $e$
Inputs 15-23: No additional constraints.

Problem credits: Benjamin Qi

Source: USA Computing Olympiad.

Input Format

The first line contains $N$ and $M$ . Then follow $M$ lines, the $e$ th containing the endpoints $(a_{e}, b_{e})$ of the $e$ th edge ( $1 \leq a_{e} < b_{e} \leq N$ ). It is guaranteed that these edges form a connected graph, and at most one edge connects each pair of vertices.

Output Format

Output $N$ lines, where the $i$ th line should contain the return value of the process starting at vertex $i$ .

Sample Input 1

3 2 1 2 2 3

Sample Output 1

12 12 21

Sample Input 2

5 6 1 2 3 4 2 4 2 3 2 5 1 5

Sample Output 2

1325 1325 2315 2315 5132

Sample Input 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

Sample Output 3

678925929 678925929 678862929 678787329 678709839 678632097 178554320 218476543 321398766 431520989 542453212 653475435 764507558 875540761 986574081

Submit

Language