P9454 [ZSHOI-R1] City Tour.

After many years of development by the king of Country X, her country has undergone a major transformation and stood out from those countries that have $n$ cities but only $n-1$ roads. In other words, Country X is no longer a tree, but a graph.

In order to centralize her power and stabilize the city-states, the king has very strict requirements on the road design: **between any two cities, there is at most one path that does not pass through the capital**. However, no one knows why this can better stabilize Country X. One day, the king of Country X decided to visit all the cities. She informed all the cities of this good news by radio the day before the tour. The enthusiastic people also responded actively, preparing to welcome the king. The king can visit only one city per day, and on the first day she will start from the capital. On each following day, she will randomly choose **with equal probability** one **unvisited city** from the cities directly connected to her current city, and go there. If there is no such city, she will immediately **return along the original path**, going back via the road she used to arrive at this city, and then repeat the above process. Because there is a portal carrying cosmic rays, this returning process **does not consume time**. The people who love her want to know the expected date when their king arrives at their city for the first time (the day she visits the capital is counted as $1$, and then it increases by $1$ once per day). Output the answer modulo $998244353$. It is guaranteed that the graph formed by the cities is connected, has no self-loops or multiple edges, and the capital is numbered $1$.

The first line contains two integers $n,m$, representing the number of cities and the number of roads in Country X. The next $m$ lines each contain two integers $u,v$, indicating a road between the two cities.

There is $1$ line containing $n$ integers. The $i$-th integer represents the expectation for city $i$.

For all testdata, $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 | $\leqslant10^4$ | $n-1$ | | 6~8 | $\leqslant10^4$ | $n$ | | 9~10 | $\leqslant10^4$ | $2n-3$ | | 11~15 | $\leqslant10^4$ | $\leqslant2\times10^4$ | | 16~20 | $\leqslant5\times10^5$ | $\leqslant6\times10^5$ | Translated by ChatGPT 5