###decription Cuber QQ knows about DFS on an undirected tree, he’s sure that you are familiar with it too. In case you are not, Cuber QQ is delighted to share with you a snippet of pseudo code:
function dfs(int cur, int parent): print(‘(‘) for all nxt that cur is adjacent to: dfs(nxt, cur) print(‘)’)
You might notice that Cuber QQ print a “(“ when entering a node, and a “)” when leaving a node. So when he finishes this DFS, in his console, he will see a bracket sequence of length 2n, where n is the number of vertices in the tree.
Obviously, if the tree is undirected and the nodes are unlabelled (meaning that all the nodes are treated equally), you can get a lot of different bracket sequences when you do the DFS. There are two reasons accounting for this. Firstly, when you are at cur, you can follow any permutation of the nodes that cur is adjacent to when you visit nxt. Secondly, the entrance to the tree, that is the root, is undeterministic when you start your DFS.
So Cuber QQ couldn’t help wondering how many distinct bracket sequences he can get possibly. As the answer can be very large, output it modulo 998 244 353.
###input The first line of the input consists of one integer t $(1≤t≤10^5)$, which is the number of the test cases.
For each test case, the tree is given in a standard format, which you might be very familiar with: first line n $(1≤n≤10^5)$, the size of tree; then n−1 lines, each consisting of two space-separated integers u, v (1≤u,v≤n, u≠v), denoting an edge.
The sum of n from all test cases does not exceed $3.2×10^6$.
###output For each test case, output the answer in one line.
#define get64(a,b) ((a)*2000000000ll+(b)) typedef pair<int,int> pii; #define __int64 long long
constint maxn=2e5+5;
// tree 节点0不准使用 int head[maxn];// point int to[maxn*2],nex[maxn*2],tot;// edge inlinevoid _addedge(int u,int v){to[++tot]=v,nex[tot]=head[u],head[u]=tot;} inlinevoidaddedge(int u,int v){_addedge(u,v),_addedge(v,u);} voiddeltree(int rt,int father){// deltree() and also don't forget tot for(int i=head[rt];i;i=nex[i]) if(to[i]!=father) deltree(to[i],rt); head[rt]=0; } // struct tree{int rt,n;}
//tree hash int pw[maxn*2]={1},hshmod;//pw要两倍 int *hsh,siz[maxn]; //point int *ehsh; //edge voiddfs(int u,int father){ siz[u]=1; for(int i=head[u];i;i=nex[i]){ if(to[i]==father)continue; dfs(to[i],u), siz[u]+=siz[to[i]]; } } voiddfs1(int u,int father){// solve every edge from father->u for(int i=head[u];i;i=nex[i]){ if(to[i]==father) continue; dfs1(to[i],u);
vector<pii>pre(buf),suf(buf);// 对后面进行处理 int sz=suf.size(); for(int i=1,j=sz-2;i<sz;i++,j--){ pre[i].first=(1ll*pre[i-1].first*pw[pre[i].second]+pre[i].first)%hshmod;// merge i-1 and i suf[j].first=(1ll*suf[j].first*pw[suf[j+1].second]+suf[j+1].first)%hshmod;// merge j and j+1 pre[i].second+=pre[i-1].second; suf[j].second+=suf[j+1].second; }
for(int i=head[u];i;i=nex[i]){ if(father==to[i]) continue; ehsh[i^1]=1;//左边放1 int idx=lower_bound(buf.begin(),buf.end(),pii(ehsh[i],2*siz[to[i]]))-buf.begin(); if(idx-1>=0) ehsh[i^1]=(1ll*ehsh[i^1]*pw[pre[idx-1].second]+pre[idx-1].first)%hshmod;// 前缀 if(idx+1<sz) ehsh[i^1]=(1ll*ehsh[i^1]*pw[suf[idx+1].second]+suf[idx+1].first)%hshmod;// 后缀 ehsh[i^1]=(1ll*ehsh[i^1]*pw[1]+2)%hshmod;//右边放2 dfs2(to[i],u,rt); } } voidtreehash(int u,int*hsh_,int*ehsh_,int base,int hshmod_){//hash all tree of tree u hsh=hsh_,ehsh=ehsh_,hshmod=hshmod_; dfs(u,0); for(int i=1;i<=siz[u]*2;i++) pw[i]=1ll*pw[i-1]*base%hshmod; dfs1(u,0),dfs2(u,0,u); } ////// end
int myhsh[4][maxn],ans[maxn]; // point int myehsh[4][maxn*2],eans[maxn*2]; // edge voiddfs3(int u,int father){// solve edge from father->u for(int i=head[u];i;i=nex[i]){ if(to[i]==father) continue; dfs3(to[i],u);