| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 93 | 56 | 48 | 62.338% |
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:
Determine all the return values of this process.
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.
Output $N$ lines, where the $i$th line should contain the return value of the process starting at vertex $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
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ドル$.
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
Make sure to output the answers modulo 10ドル^9+7$.