这是一个交互问题。
给定一个有根树$$$^{\text{*}}$$$ $$$T$$$,大小为$$$m$$$,其中每个节点$$$i$$$都有一个关联值$$$a_i$$$,定义一个 垂直路径 作为节点序列 $$$[s_1,s_2,\ldots,s_p]$$$,使得 $$$s_{i+1}$$$ 是所有 $$$1 \leq i \lt p$$$ 的 $$$s_i$$$ 的子节点。垂直路径是 好 if $$$\operatorname{gcd}(a_{s_1},a_{s_2},\ldots,a_{s_p}) \neq 1$$$$$$^{\text{†}}$$$。将 $$$f(T)$$$ 定义为良好垂直路径的最小数量,使得每个节点都位于 正是 一条好路。
有一个奇怪的有 $$$n$$$ 节点的有根树,其中节点 $$$1$$$ 是根。该树满足每个节点仅具有标签大于其自身的子节点的属性。将 $$$S(u)$$$ 表示为节点 $$$u$$$ 的子树。也就是说,$$$S(u)$$$ 包含所有节点 $$$v$$$,使得从节点 $$$1$$$ 到节点 $$$v$$$ 的最短路径包含节点 $$$u$$$,以及两个端点位于两个此类节点之间的所有边。
您有兴趣查找 $$$f(S(n)), f(S(n-1)), \ldots, f(S(1))$$$。然而,有一个神奇的神谕向您隐藏了有关这棵树的信息!具体来说,预言机仅在读取 $$$f(S(x+1))$$$ 的结果后才告诉你有关顶点 $$$x$$$ 的信息。换句话说,你必须在线解决这个问题,从节点$$$n$$$开始,到节点$$$1$$$结束。
$$$^{\text{*}}$$$树是没有环的连通图。 有根树是一棵树,其中一个顶点是特殊的,称为根。 顶点 $$$v$$$ 的父顶点是从 $$$v$$$ 到根的简单路径上的第一个顶点。根没有父级。 顶点 $$$v$$$ 的子节点是任何以 $$$v$$$ 为父节点的顶点 $$$u$$$。
$$$^{\text{†}}$$$这里,$$$\gcd(x, y)$$$表示整数$$$x$$$和$$$y$$$的最大公约数(GCD)。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 2\cdot 10^5$$$) – 表示树中的节点数。
然后是 $$$n$$$ 行。其中第 $$$i$$$ 行将包含有关节点 $$$j=n-i+1$$$ 的信息,格式如下。
- $$$a_j \; k \; c_1 \; c_2 \; \l点\; c_k$$$:节点 $$$j=n-i+1$$$ 具有关联值 $$$a_j$$$ 和带有节点标签 $$$c_1,c_2,\ldots,c_k$$$ 的 $$$k$$$ 子节点。
对于每个节点 $$$j$$$,保证 $$$2 \le a_j \le 10^{18}$$$ 和 $$$j+1 \le c_i \le n$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。
保证一个测试用例中所有节点的 $$$k$$$ 之和恰好为 $$$n-1$$$,并且边形成一棵有效的有根树。
输出
对于每个测试用例,您必须输出 $$$n$$$ 行,其中第 $$$i$$$ 行包含 $$$f(S(n-i+1))$$$ 的值。
请注意,此问题在技术上是交互式的。具体来说,交互器只有在读取您的输出行后才会为您提供下一条信息。
打印每个后 线,您必须输出行尾并刷新$$$^{\text{*}}$$$ 输出。否则,你会得到 超出空闲限制 判决。
$$$^{\text{*}}$$$要刷新,请使用:
- fflush(标准输出) or cout.flush() 在 C++ 中;
- sys.stdout.flush() 在 Python 中;
- 请参阅其他语言的文档。
示例
输入复制
4 5 11 0 7 0 5 0 3 2 4 5 2 2 2 3 5 10 0 8 0 6 0 4 0 2 4 2 3 4 5 6 221 0 143 1 6 77 1 5 35 1 4 15 1 3 6 1 2 3 1000000000000000000 0 999999999999999998 0 999999999999999998 2 3 2
输出复制
1 1 1 3 5 1 1 1 1 4 1 1 2 2 3 3 1 1 2
注意
在第一个测试用例中,由于 $$$a_i$$$ 的所有值都是互质的,因此每条路径不可能覆盖多个节点。因此,$$$f(S(1))$$$ 的值为$$$5$$$。
在第二个测试用例中,我们可以使用以下 $$$4$$$ 垂直路径验证 $$$f(S(1))=4$$$ :
- $$$[1,2]$$$。这条垂直路径的GCD是$$$\operatorname{gcd}(2,4)=2$$$。
- $$$[3]$$$。这条垂直路径的GCD为$$$\operatorname{gcd}(6)=6$$$。
- $$$[4]$$$。这条垂直路径的GCD为$$$\operatorname{gcd}(8)=8$$$。
- $$$[5]$$$。这条垂直路径的GCD为$$$\operatorname{gcd}(10)=10$$$。
由于没有垂直路径的 GCD 为 $$$1$$$,因此该解决方案是有效的。此外,我们可以证明不可能用少于 $$$4$$$ 垂直路径覆盖所有节点。