{"raw_statement":[{"iden":"background","content":"原题链接：<https://oier.team/problems/S1C>。"},{"iden":"statement","content":"给定一张包含 $n$ 个点 $m$ 条边的简单无向连通图，点的编号为 $1\\sim n$。\n\n你需要求出有多少集合对 $S,T\\sube \\{1,2,\\dots,n\\}$，满足对于任意的 $i\\in S$，要么 $i$ 也 $\\in T$，要么存在 $x,y\\in T$（$x\\neq y$），满足存在一条从 $x$ 到 $y$ 的简单路径经过 $i$。\n\n注意，集合对 $S,T$ 可以为空集。\n\n输出答案对 $998244353$ 取模后的结果。\n"},{"iden":"input","content":"第一行两个正整数 $n,m$。\n\n接下来 $m$ 行，每行两个正整数 $u_i,v_i$，描述图上的一条边。保证图连通，无自环、重边。"},{"iden":"output","content":"共一行一个整数，表示满足题目条件的集合对 $S,T$ 的数量对 $998244353$ 取模后的结果。"},{"iden":"note","content":"__【样例解释 1】__\n\n所有合法的集合 $S,T$ 为：\n\n1. $S=\\{\\},T=\\{\\}$。\n2. $S=\\{\\},T=\\{1\\}$。\n3. $S=\\{\\},T=\\{2\\}$。\n4. $S=\\{\\},T=\\{1,2\\}$。\n5. $S=\\{1\\},T=\\{1\\}$。\n6. $S=\\{1\\},T=\\{1,2\\}$。\n7. $S=\\{2\\},T=\\{2\\}$。\n8. $S=\\{2\\},T=\\{1,2\\}$。\n9. $S=\\{1,2\\},T=\\{1,2\\}$。 \n\n__【数据范围】__\n\n__本题使用子任务捆绑测试。__\n\n对于 $100\\%$ 的数据，$2\\le n\\le 5\\times 10^5$，$n-1\\le m\\le 10^6$，$1\\le u_i,v_i\\le n$。保证图连通，无自环、重边。\n\n| 子任务编号 | $n\\le $        | $m\\le $            | 特殊性质        | 分值 |\n| ---------- | -------------- | ------------------ | --------------- | ---- |\n| $1$        | $10$           | $\\frac{n(n-1)}{2}$ | 无              | $10$ |\n| $2$        | $20$           | $\\frac{n(n-1)}{2}$ | 无              | $10$ |\n| $3$        | $5\\times 10^5$ | $n-1$              | $u_i=i,v_i=i+1$ | $10$ |\n| $4$        | $5\\times 10^5$ | $n-1$              | 无              | $20$ |\n| $5$        | $5\\times 10^5$ | $n$                | 无              | $20$ |\n| $6$        | $5\\times 10^5$ | $10^6$             | 无              | $30$ |\n"}],"translated_statement":null,"sample_group":[["2 1\n1 2","9"],["9 10\n8 3\n6 8\n8 5\n1 6\n6 2\n4 6\n8 2\n1 7\n9 6\n5 3","80995"],["20 36\n4 7\n2 13\n18 11\n6 14\n4 20\n5 4\n1 9\n19 4\n6 8\n11 15\n4 11\n4 18\n16 9\n16 4\n18 15\n3 18\n4 6\n5 7\n20 6\n20 8\n8 14\n19 13\n12 9\n4 8\n4 15\n20 14\n3 10\n12 1\n17 16\n13 4\n4 14\n10 18\n4 2\n16 12\n19 2\n1 16","211240350"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}