Egor 和他的朋友 Arseniy 今年即将完成学业,即将进入大学。由于他们都是非常负责任的人,所以他们已经开始准备入学了。
首先,他们决定在漫长的四年学习中照顾自己的住处,在访问大学网站后,他们发现大学宿舍可以表示为一棵有 $$$n$$$ 个顶点的根树,根位于顶点 $$$1$$$。在树中,每个顶点代表具有某种类型活动 $$$a_i$$$ 的娱乐活动。朋友们需要选择 $$$2$$$ 的娱乐活动(不一定不同)来定居。这些人相信,以下函数 $$$f(u, v) = diff(u, lca(u, v)) \cdot diff(v, lca(u, v))$$$ 的价值越大,他们的生活就会越有趣。帮助 Egor 和 Arseniy 找出所有游戏对中 $$$f(u, v)$$$ 的最大值!
$$$^{\dagger} diff(u, v)$$$ — 从顶点 $$$u$$$ 到顶点 $$$v$$$ 的简单路径上列出的不同活动的数量。
$$$^{\dagger} lca(u, v)$$$ — 一个顶点 $$$p$$$,与根的距离最大,并且是顶点 $$$u$$$ 和顶点 $$$v$$$ 的父节点。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 测试用例的数量。然后是测试用例的描述。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^{5}$$$)。
每个测试用例的第二行包含 $$${n - 1}$$$ 整数 $$$p_2, p_3, \ldots,p_n$$$ ($$$1 \le p_i \le i - 1$$$),其中 $$$p_i$$$ — 顶点 $$$i$$$ 的父节点。
每个测试用例的第三行包含 $$${n}$$$ 整数 $$$a_1, a_2, \ldots,a_n$$$ ($$$1 \le a_i \le n$$$),其中 $$$a_i$$$ — 位于顶点 $$$i$$$ 处的活动编号。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。
输出
对于每个测试用例,输出所有游戏对 $$$(u, v)$$$ 的 $$$f(u, v)$$$ 的最大值。
示例
输入 #1
4 2 1 1 2 7 1 1 2 2 3 3 6 5 2 3 6 5 6 13 1 1 1 2 2 2 3 3 4 5 6 6 2 2 2 1 4 9 7 2 5 2 1 11 2 12 1 1 1 2 2 3 4 4 7 7 6 11 2 1 11 12 8 5 8 8 5 11 7
输出 #1
2 9 9 12
注意
考虑第四个测试用例。该树具有以下结构: