#P17969. Not a Work of Idol 2

Not a Work of Idol 2

Not a Work of Idol 2

给定一棵有 nn 个顶点的树,顶点编号为 1,…,n1,\ldots,n。

给每个顶点 ii 分配一个整数 pip_i,要求 p1,…,pnp_1,\ldots,p_n 是 1,…,n1,\ldots,n 的一个排列,且对树上的每条边 (u,v)(u,v),都有

pu+pv≤n+1.p_u+p_v\le n+1.

求满足条件的排列数量,对 44 取模。

输入格式

第一行是测试用例数 T≥1T\ge1。每组数据第一行包含 nn,接下来 n−1n-1 行,每行包含两个不同顶点 ui,viu_i,v_i,表示树的一条边。

1≤n≤1061\le n\le10^6。保证给出的边构成一棵树。所有测试用例的 nn 之和不超过 10610^6。

输出格式

每组数据输出一行一个整数,表示合法排列数量对 44 取模的结果。

样例输入

4
1
2
1 2
4
3 1
2 1
2 4
4
4 3
3 1
2 3

样例输出

1
2
0
2