定义一个函数 $$$f$$$,使得对于数组 $$$b$$$,$$$f(b)$$$ 返回前缀最大值为 $$$b$$$ 的数组。换句话说, $$$f(b)$$$ 是一个仅包含 $$$b_i$$$ 元素的数组,其中 $$$b_i=\max(b_1,b_2,\ldots,b_i)$$$,而不改变它们的顺序。例如,$$$f([3,10,4,10,15,1])=[3,10,10,15]$$$。
给你一棵由 $$$n$$$ 节点组成的树,根节点为 $$$1$$$。
如果对于所有 $$$i$$$ 满足以下条件,则 $$$^\dagger$$$ $$$p$$$ 的排列被视为树的前序:
- 令 $$$k$$$ 为节点 $$$p_i$$$ 的真后代 $$$^\ddagger$$$ 的数量。
- 对于所有$$$x$$$,使得$$$i < x \leq i+k$$$,$$$p_x$$$ 是节点$$$p_i$$$ 的真后代。
找出所有可能的预购 $$$a$$$ 中 $$$f(a)$$$ 的不同值的数量。由于该值可能很大,因此您只需对 $$$998\,244\,353$$$ 求模即可。
$$$^\dagger$$$ 长度 $$$n$$$ 的排列是一个数组,由 $$$n$$$ 不同的整数组成,从 $$$1$$$ 到 $$$n$$$ 的任意顺序。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。
$$$^\ddagger$$$ 节点 $$$t$$$ 是节点 $$$s$$$ 的真后代,如果 $$$s \neq t$$$ 和 $$$s$$$ 位于从 $$$t$$$ 到 $$$1$$$ 的唯一简单路径上。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^6$$$) — 顶点数。
接下来的 $$$n-1$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$) - 表示节点 $$$u$$$ 和 $$$v$$$ 之间的边。保证给定的边形成一棵树。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^6$$$。
输出
对于每个测试用例,输出 $$$f(a)$$$ 模 $$$998\,244\,353$$$ 可以得到的不同值的数量。
示例
输入 #1
6 1 2 1 2 3 1 2 1 3 3 1 2 2 3 5 1 2 1 3 1 4 1 5 10 1 2 2 3 1 4 2 5 2 6 4 7 5 8 4 9 9 10
输出 #1
1 1 2 1 8 6
注意
在第一个测试用例中,唯一有效的预订是 $$$a=[1]$$$。所以 $$$f(a)$$$ 唯一可能的值为 $$$[1]$$$。
在第二个测试用例中,唯一有效的预订是 $$$a=[1,2]$$$。所以唯一可能的值 $$$f(a)$$$ 是 $$$[1,2]$$$。
在第三个测试用例中,两个有效的预订单是 $$$a=[1,2,3]$$$ 和 $$$a=[1,3,2]$$$。因此 $$$f(a)$$$ 的可能值为 $$$[1,2,3]$$$ 和 $$$[1,3]$$$。
在第五个测试用例中,$$$f(a)$$$ 的可能值为:
- $$$[1,5]$$$;
- $$$[1,2,5]$$$;
- $$$[1,3,5]$$$;
- $$$[1,4,5]$$$;
- $$$[1,2,3,5]$$$;
- $$$[1,2,4,5]$$$;
- $$$[1,3,4,5]$$$;
- $$$[1,2,3,4,5]$$$.