{"trustable":false,"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":"In freshman year I was really scared of graph theory. I could study all the algorithms in the world but I would never step one foot in the realm of graphs. Graphs used to scare me. \u003cbr\u003e\u003cbr\u003e\nOne day, I had no video games left in my PC, no tv series left to watch, no new movies would interest me, so I had to do something to not get bored. I was turning pages of one of the books I own, and became brave (!) enough to read what graph actually is. That was the day I set foot on the scary (!) realm of graph theory. \u003cbr\u003e\u003cbr\u003e\n\nI learnt DFS and BFS and I thought if any problem can really be modeled into graph, that would be really cool. I started studying more about graph theory, and the I suddenly came across this scary graph problem, and after solving this I was never scared of graphs any more! So, are you ready to overcome your fear of graph theory and solve this problem?\u003cbr\u003e\u003cbr\u003e\n\nI will give you a scary(!), undirected, unweighted graph consisting of \u003ci\u003en\u003c/i\u003e vertices and \u003ci\u003em\u003c/i\u003e edges.\u003cbr\u003e\u003cbr\u003e\n\nYou have to write a number on each vertex of the graph. Each number should be 1, 2 or 3. The graph becomes \"shera\" if for each edge the sum of numbers on vertices connected by this edge is odd.\u003cbr\u003e\u003c/br\u003e\n\nCalculate the number of possible ways to write numbers 1, 2 and 3 on vertices so the graph becomes \"shera\". Since this number may be large, print it modulo 998244353. \u003cbr\u003e\u003c/br\u003e\n\nNote that you have to write exactly one number on each vertex.\u003cbr\u003e\u003cbr\u003e\n\nThe graph does not have any self-loops or multiple edges.\u003cbr\u003e\u003cbr\u003e\n\nCan you turn this scary graph into a shera graph?"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains one integer t (1 ≤ t ≤ 3 * 10\u003csup\u003e5\u003c/sup\u003e) — the number of tests in the input.\u003c/p\u003e\n\u003cp\u003eThe first line of each test contains two integers \u003ci\u003en\u003c/i\u003e and \u003ci\u003em\u003c/i\u003e (1 ≤ n ≤ 3 * 10\u003csup\u003e5\u003c/sup\u003e, 0 ≤ m ≤ 3 * 10\u003csup\u003e5\u003c/sup\u003e) — the number of vertices and the number of edges, respectively. Next \u003ci\u003em\u003c/i\u003e lines describe edges: \u003ci\u003ei\u003c/i\u003e-th line contains two integers u\u003csub\u003ei\u003c/sub\u003e, v\u003csub\u003ei\u003c/sub\u003e (1 ≤ u\u003csub\u003ei\u003c/sub\u003e, v\u003csub\u003ei\u003c/sub\u003e ≤ n; u\u003csub\u003ei\u003c/sub\u003e ≠ v\u003csub\u003ei\u003c/sub\u003e) — indices of vertices connected by \u003ci\u003ei\u003c/i\u003e-th edge.\u003c/p\u003e\n\u003cp\u003eIt is guaranteed that total number all nodes for in test cases ≤ 3 * 10\u003csup\u003e5\u003c/sup\u003e and total number of edges in all test cases ≤ 3 * 10\u003csup\u003e5\u003c/sup\u003e.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"For each test print one line, containing one integer — the number of possible ways to write numbers 1, 2, 3 on the vertices of given graph so it becomes beautiful. Since answers may be large, print them modulo 998244353."}},{"title":"Example","value":{"format":"HTML","content":"\u003cdiv class\u003d\"sample-test\"\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e2\n2 1\n1 2\n4 6\n1 2\n1 3\n1 4\n2 3\n2 4\n3 4\n\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e4\n0\n\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003ePossible ways to distribute numbers in the first test: \u003c/p\u003e\n\u003col\u003e \n \u003cli\u003e the vertex 1 should contain 1, and 2 should contain 2; \u003c/li\u003e\n \u003cli\u003e the vertex 1 should contain 3, and 2 should contain 2; \u003c/li\u003e\n \u003cli\u003e the vertex 1 should contain 2, and 2 should contain 1; \u003c/li\u003e\n \u003cli\u003e the vertex 1 should contain 2, and 2 should contain 3. \u003c/li\u003e\n\u003c/ol\u003e\n\u003cp\u003eIn the second test there is no way to distribute numbers.\u003c/p\u003e"}}]}