{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e给定一个由$$$n$$$个顶点和$$$m$$$条边组成的无向无权图。\u003c/p\u003e\u003cp\u003e你需要在图的每个顶点上写一个数字。每个数字应为$$$1$$$、$$$2$$$或$$$3$$$。如果对于每条边,连接该边的顶点上的数字之和为奇数,则图变得美丽。\u003c/p\u003e\u003cp\u003e计算在顶点上写下数字$$$1$$$、$$$2$$$和$$$3$$$的可能方法数量,使得图变得美丽。由于这个数量可能很大,输出结果对$$$998244353$$$取模。\u003c/p\u003e\u003cp\u003e\u003cspan class\u003d\"tex-font-style-bf\"\u003e请注意,你必须在每个顶点上写下一个数字\u003c/span\u003e。\u003c/p\u003e\u003cp\u003e图中没有自环或重边。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e第一行包含一个整数$$$t$$$($$$1 \\le t \\le 3 \\cdot 10^5$$$)— 输入中的测试数量。\u003c/p\u003e\u003cp\u003e每个测试的第一行包含两个整数$$$n$$$和$$$m$$$($$$1 \\le n \\le 3 \\cdot 10^5, 0 \\le m \\le 3 \\cdot 10^5$$$)— 顶点数和边数。接下来$$$m$$$行描述边:第$$$i$$$行包含两个整数$$$u_i$$$、$$$ v_i$$$($$$1 \\le u_i, v_i \\le n; u_i \\neq v_i$$$)— 连接第$$$i$$$条边的顶点的索引。\u003c/p\u003e\u003cp\u003e保证$$$\\sum\\limits_{i\u003d1}^{t} n \\le 3 \\cdot 10^5$$$和$$$\\sum\\limits_{i\u003d1}^{t} m \\le 3 \\cdot 10^5$$$。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e对于每个测试,输出一行,包含一个整数 — 在给定图的顶点上写下数字$$$1$$$、$$$2$$$、$$$3$$$的可能方法数量,使其变得美丽。由于答案可能很大,输出结果对$$$998244353$$$取模。\u003c/p\u003e"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n2 1\n1 2\n4 6\n1 2\n1 3\n1 4\n2 3\n2 4\n3 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\n0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"注意","value":{"format":"HTML","content":"\u003cp\u003e第一个测试中分配数字的可能方法:\u003c/p\u003e\u003col\u003e \u003cli\u003e 顶点$$$1$$$应包含$$$1$$$,顶点$$$2$$$应包含$$$2$$$; \u003c/li\u003e\u003cli\u003e 顶点$$$1$$$应包含$$$3$$$,顶点$$$2$$$应包含$$$2$$$; \u003c/li\u003e\u003cli\u003e 顶点$$$1$$$应包含$$$2$$$,顶点$$$2$$$应包含$$$1$$$; \u003c/li\u003e\u003cli\u003e 顶点$$$1$$$应包含$$$2$$$,顶点$$$2$$$应包含$$$3$$$。 \u003c/li\u003e\u003c/ol\u003e\u003cp\u003e在第二个测试中,没有分配数字的方法。\u003c/p\u003e"}}]}