Skip to content
Sign in

A Graph Problem

Unrated
English

Language

Contribute a translation
Time limit
2000 ms
Memory limit
256 MB
Submissions
0
Correct
0
Solved by
0
AC rate
—

Statement

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\le N\le 2\cdot 10^5$, $N-1\le M\le 4\cdot 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\pmod{10^9+7}$.

​ Determine all the return values of this process. ​

Input

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\le a_e<b_e\le N$). It is guaranteed that these edges form a connected graph, and at most one edge connects each pair of vertices.

​

Scoring

  • Input 4: $N,M\le 2000$
  • Inputs 5-6: $N\le 2000$
  • Inputs 7-10: $N\le 10000$
  • Inputs 11-14: $a_e+1=b_e$ for all $e$
  • Inputs 15-23: No additional constraints.

Output

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

Examples

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

Notes

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 $10^9+7$.

Tags

No tags yet

Source