题目描述
Problem Background
Under the long-term construction of the King of Country X, her nation has undergone a qualitative transformation, standing out from the numerous countries with only $n$ cities and $n-1$ roads. That is to say, Country X is no longer a tree but a graph.
Problem Description
To centralize her power and stabilize the city-states, the King has strict requirements for the national road design. There is at most one path between any two cities that does not pass through the capital. Although no one knows why this can better stabilize Country X.
One day, the King of Country X decided to patrol all the cities. She announced this good news to all cities via radio the day before the patrol. The enthusiastic citizens also responded actively, preparing to welcome the King's arrival.
The King can visit only one city per day, and she will start from the capital on the first day.
For each subsequent day, she will randomly choose a city directly connected to her current city that she has not visited before, with equal probability. If no such city exists, she will immediately return the way she came, repeating the above operation, as the process is time-free due to the teleportation gate with cosmic rays.
The citizens who love her want to know the expected date of their King's first visit to their city (the day she visits the capital is $1$, and each subsequent day adds $1$), the answer should be modulo $998244353$.
The graph formed by the cities is guaranteed to be connected, with no self-loops or multiple edges, and the capital is numbered $1$.
Input Format
The first line contains two numbers $n, m$, representing the number of cities and the number of paths in Country X.
The next $m$ lines each contain two numbers $u, v$ representing a path between cities.
Output Format
A single line with $n$ numbers.
The $i$-th number represents the expected date for city $i$.
Sample Input and Output
Sample Input #1
3 2
1 2
2 3
Sample Output #1
1 2 3
Sample Input #2
4 3
1 2
2 3
2 4
Sample Output #2
1 2 499122180 499122180
Sample Input #3
5 7
5 4
2 4
4 3
1 3
1 2
1 4
1 5
Sample Output #3
1 249561092 249561092 249561091 249561092
Notes
For all data points, $1 \leqslant n \leqslant 5 \times 10^5$, $1 \leqslant m \leqslant 6 \times 10^5$.
| Data Point | n | m |
|---|---|---|
| 1~2 | $5$ | $7$ |
| 3~5 | $\leqslant 10^4$ | $n-1$ |
| 6~8 | $\leqslant 10^4$ | $n$ |
| 9~10 | $\leqslant 10^4$ | $2n-3$ |
| 11~15 | $\leqslant 10^4$ | $\leqslant 2 \times 10^4$ |
| 16~20 | $\leqslant 5 \times 10^5$ | $\leqslant 6 \times 10^5$ |
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分