问题描述

Farmer John 对不同奶牛品种的进化进行了广泛的研究。所得到的结果形成一棵 N（2≤N≤10^5）个结点的有根树，编号为 1…N，每个结点对应一个奶牛品种。对于每一个 i∈[2,N]，结点 i 的父结点是结点 pi（1≤pi<i），意味着品种 i 是由品种 pi 进化而来的。称结点 j 为结点 i 的祖先，如果 j=pi 或者 j 是 pi 的祖先。

树中的结点 i 所关联的品种具有整数 si 数量的斑点。定义树的「不平衡度」为所有结点对 (i,j) 中 |si−sj| 的最大值，其中 j 是 i 的祖先。

Farmer John 不知道每个品种的 si 的确切数值，但他知道这些值的下界和上界。你的任务是为每个结点分配一个整数值 si∈[li,ri]（0≤li≤ri≤109），以最小化树的不平衡度。

输入格式

输入的第一行包含 T（1≤T≤10），为需要独立求解的子测试用例的数量，以及一个整数 B∈{0,1}。

每个子测试用例的第一行包含 N，第二行包含 N−1 个整数 p2,p3,…,pN。

以下 N 行每行包含两个整数 li 和 ri。

输入保证所有子测试用例的 N 之和不超过 10^5。

输出格式

对每个子测试用例，根据 B 的值输出一行或两行。 每个子测试用例的第一行包含最小不平衡度。

如果 B=1，则再输出一行，包含 N 个空格分隔的整数 s1,s2,…,sN，为达到以上不平衡度的一种斑点数量的分配方式。任何合法的分配方式均正确。

输入样例1：

3 0
3
1 1
0 100
1 1
6 7
5
1 2 3 4
6 6
1 6
1 6
1 6
5 5
3
1 1
0 10
0 1
9 10

输出样例1：

3
1
4

对于第一个子测试用例，最小不平衡度为 3。一种达到不平衡度 3 的方式是令 [s1,s2,s3]=[4,1,7]。

输入样例2：

3 1
3
1 1
0 100
1 1
6 7
5
1 2 3 4
6 6
1 6
1 6
1 6
5 5
3
1 1
0 10
0 1
9 10

输出样例2：

3
3 1 6
1
6 5 5 5 5
4
5 1 9

这个测试用例除了 B 的值之外与第一个测试用例完全相同。另一种达到不平衡度 3 的方式是令 [s1,s2,s3]=[3,1,6]。

测试点性质：

测试点 3-4 对于所有的 i 满足 li=ri。

测试点 5-6 对于所有的 i 满足 pi=i−1。

测试点 7-16 没有额外限制。

在每一部分子任务中，前一半的测试点满足 B=0，后一半测试点满足 B=1。

供题：Andrew Wang