{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eCuber QQ 对无向树上的深度优先搜索很了解,他确信你也很熟悉。如果你不熟悉的话,Cuber QQ 很高兴与你分享伪代码片段:\u003cbr\u003e\u003cbr\u003e\u003cpre\u003e\u003cbr\u003efunction dfs(int cur, int parent):\u003cbr\u003e print(`(`)\u003cbr\u003e for all nxt that cur is adjacent to:\u003cbr\u003e dfs(nxt, cur)\u003cbr\u003e print(`)`)\u003cbr\u003e\u003c/pre\u003e\u003cbr\u003e\u003cbr\u003e你可能注意到,Cuber QQ 在进入一个节点时打印“(”,在离开一个节点时打印“)”。因此,当他完成这次深度优先搜索时,在他的控制台中,他会看到一个长度为$2n$的括号序列,其中$n$是树中顶点的数量。\u003cbr\u003e\u003cbr\u003e显然,如果树是无向的,节点没有标记(意味着所有节点都是平等对待的),在进行深度优先搜索时,你可以得到许多不同的括号序列。这有两个原因。首先,当你在 cur 时,你可以在访问 nxt 时遵循 cur 相邻的任意节点的任意排列。其次,在开始深度优先搜索时,树的入口,也就是根节点,是不确定的。\u003cbr\u003e\u003cbr\u003e因此,Cuber QQ 忍不住想知道他可能得到多少个不同的括号序列。由于答案可能非常大,输出它对$998~244~353$取模的结果。\u003cbr\u003e\u003cbr\u003e\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"输入的第一行包含一个整数$t$($1 \\le t \\le 10^5$),表示测试用例的数量。\u003cbr\u003e\u003cbr\u003e对于每个测试用例,树以标准格式给出,你可能非常熟悉:第一行$n$($1 \\le n \\le 10^5$),树的大小;然后$n-1$行,每行包含两个用空格分隔的整数$u$,$v$($1 \\le u, v \\le n$,$u \\ne v$),表示一条边。\u003cbr\u003e\u003cbr\u003e所有测试用例中$n$的总和不超过$3.2 \\times 10^6$。"}},{"title":"输出","value":{"format":"HTML","content":"对于每个测试用例,输出一行答案。"}},{"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\u003e3\r\n4\r\n1 3\r\n2 3\r\n4 3\r\n5\r\n1 2\r\n2 3\r\n3 4\r\n4 5\r\n5\r\n1 2\r\n2 3\r\n3 4\r\n3 5\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n4\r\n8\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}