{"raw_statement":[{"iden":"background","content":"在 X 国国王多年的建设之下，她的国家发生了质的蜕变，从众多 $n$ 座城市却只有 $n-1$ 条道路的国家中脱颖而出。也就是说，X 国不再是一棵树了，而是一张图。"},{"iden":"statement","content":"国王为了能够集中自己的权力，稳固城邦，她对国家道路设计要求十分严苛，**任何两个城市之间的路径至多只有一条不经过首都**，虽然但是，没有人知道为什么这样能够更好地稳固 X 国。\n\n有一天，X 国国王决定巡视所有的城市，她通过无线电在巡城前一天向所有的城市通知了这个好消息。热情的群众们也积极地做出了响应，准备迎接国王的到来。\n\n国王一天只能造访一座城市，而且第一天她会从首都开始。\n\n在之后的每一天，她会随机从与她所在城市直接相连的城市中**等概率**地选择一个她**没有前往过的城市**前往。如果不存在这样的城市，她会立即**原路返回**，从她来这个城市的路回去，再重复上述操作，因为有携带宇宙射线的传送门，这个过程**不消耗时间**。\n\n爱戴她的群众们想要知道，他们的国王第一次到达他们所在城市的日期（她造访首都的那一天为 $1$，之后每一天一次加 $1$）的期望是多少，答案对 $998244353$ 取模。\n\n保证城市构成的图是连通图，无自环与重边，且首都编号为 $1$。"},{"iden":"input","content":"第一行有两个数 $n,m$，代表X国的城市数和路径数。\n\n接下来的 $m$ 行，每行两个数 $u,v$ 表示城市的一条路径。"},{"iden":"output","content":"共 $1$ 行，$n$ 个数。\n\n第 $i$ 个数代表 $i$ 号城市的期望。"},{"iden":"note","content":"对于所有的数据点，$1\\leqslant n\\leqslant 5 \\times 10^5$，$1\\leqslant m \\leqslant 6 \\times 10^5$。\n| 数据点 | n | m |\n| :----------: | :----------: | :----------: |\n| 1~2 | $5$ | $7$ |\n| 3~5 | $\\leqslant10^4$ | $n-1$ |\n| 6~8 | $\\leqslant10^4$ | $n$ |\n| 9~10 | $\\leqslant10^4$ | $2n-3$ |\n| 11~15 | $\\leqslant10^4$ | $\\leqslant2\\times10^4$ |\n| 16~20 | $\\leqslant5\\times10^5$ | $\\leqslant6\\times10^5$ |"}],"translated_statement":null,"sample_group":[["3 2\n1 2\n2 3","1 2 3 \n"],["4 3\n1 2\n2 3\n2 4\n","1 2 499122180 499122180 \n"],["5 7\n5 4\n2 4\n4 3\n1 3\n1 2\n1 4\n1 5\n","1 249561092 249561092 249561091 249561092 \n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}