King’s Royal Journey

The Kingdom of X is famous for its unusual road network. In this kingdom, the road planning is such that any two cities have at most one simple path that does not go through the capital. Although no one knows the reason behind this design, it is believed to have helped the king concentrate power and secure the city‐state.

One day, the king decides to tour all the cities. One day before the tour begins, she announces the good news over the radio. The enthusiastic citizens eagerly prepare to welcome her.

The king can visit one city per day, and she starts her journey at the capital on day \(1\). For every day after, from her current city she randomly and with equal probability chooses one of the directly connected cities that she has not visited before to travel to. If there is no such city, she immediately backtracks along the road she came by (using a portal that consumes no time) and repeats the process.

The citizens of the kingdom are curious: what is the expected day (with the capital visit counted as day \(1\), and each new visit adds \(1\)) on which the king will first arrive in their city? Report your answer modulo \(998244353\).

Note: It is guaranteed that the graph formed by the cities is connected and does not contain self-loops or multiple edges. The capital is numbered \(1\).

inputFormat

The first line contains two integers \(n\) and \(m\) (\(1 \leq n \leq 2\times10^5\), \(n-1 \leq m \leq 2\times10^5\)), representing the number of cities and the number of roads, respectively.

Each of the following \(m\) lines contains two integers \(u\) and \(v\) (\(1 \le u,v \le n\)) indicating that there is an undirected road between cities \(u\) and \(v\).

outputFormat

Output \(n\) integers separated by spaces, where the \(i\)-th integer is the expected day on which the king first visits city \(i\), modulo \(998244353\).

Note: The expected value is a rational number. You should output this value modulo \(998244353\) using modular arithmetic (in particular, use the modular inverse for any division operations). For example, an expected day of \(\frac{5}{2}\) should be output as \(5 \times 2^{-1} \bmod 998244353\).

sample

3 2
1 2
1 3

1 2 2