[ZSHOI-R1] 巡城

在 X 国国王多年的建设之下，她的国家发生了质的蜕变，从众多 $n$ 座城市却只有 $n-1$ 条道路的国家中脱颖而出。也就是说，X 国不再是一棵树了，而是一张图。

国王为了能够集中自己的权力，稳固城邦，她对国家道路设计要求十分严苛，**任何两个城市之间的路径至多只有一条不经过首都**，虽然但是，没有人知道为什么这样能够更好地稳固 X 国。 有一天，X 国国王决定巡视所有的城市，她通过无线电在巡城前一天向所有的城市通知了这个好消息。热情的群众们也积极地做出了响应，准备迎接国王的到来。 国王一天只能造访一座城市，而且第一天她会从首都开始。 在之后的每一天，她会随机从与她所在城市直接相连的城市中**等概率**地选择一个她**没有前往过的城市**前往。如果不存在这样的城市，她会立即**原路返回**，从她来这个城市的路回去，再重复上述操作，因为有携带宇宙射线的传送门，这个过程**不消耗时间**。 爱戴她的群众们想要知道，他们的国王第一次到达他们所在城市的日期（她造访首都的那一天为 $1$，之后每一天一次加 $1$）的期望是多少，答案对 $998244353$ 取模。 保证城市构成的图是连通图，无自环与重边，且首都编号为 $1$。

第一行有两个数 $n,m$，代表X国的城市数和路径数。 接下来的 $m$ 行，每行两个数 $u,v$ 表示城市的一条路径。

共 $1$ 行，$n$ 个数。 第 $i$ 个数代表 $i$ 号城市的期望。

3 2
1 2
2 3

1 2 3 

4 3
1 2
2 3
2 4

1 2 499122180 499122180 

5 7
5 4
2 4
4 3
1 3
1 2
1 4
1 5

1 249561092 249561092 249561091 249561092 

对于所有的数据点，$1\leqslant n\leqslant 5 \times 10^5$，$1\leqslant m \leqslant 6 \times 10^5$。 | 数据点 | 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$ |