Farmer John has conducted an extensive study of the evolution of different cow breeds. The result is a rooted tree with N (2≤N≤105) nodes labeled 1…N, each node corresponding to a cow breed. For each i∈[2,N], the parent of node i is node pi (1≤pi<i), meaning that breed i evolved from breed pi. A node j is called an ancestor of node i if j=pi or j is an ancestor of pi.
Every node i in the tree is associated with a breed having an integer number of spots si. The "imbalance" of the tree is defined to be the maximum of |si−sj| over all pairs of nodes (i,j) such that j is an ancestor of i.
Farmer John doesn't know the exact value of si for each breed, but he knows lower and upper bounds on these values. Your job is to assign an integer value of si∈[li,ri] (0≤li≤ri≤10^9) to each node such that the imbalance of the tree is minimized.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains T (1≤T≤10), the number of independent test cases to be solved, and an integer B∈{0,1}.
Each test case starts with a line containing N, followed by N−1 integers p2,p3,…,pN.
The next N lines each contain two integers li and ri.
It is guaranteed that the sum of N over all test cases does not exceed 105.
OUTPUT FORMAT (print output to the terminal / stdout):
For each test case, output one or two lines, depending on the value of B.
The first line for each test case should contain the minimum imbalance.
If B=1, then print an additional line with N space-separated integers s1,s2,…,sN containing an assignment of spots that achieves the above imbalance. Any valid assignment will be accepted.
SAMPLE INPUT:
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
SAMPLE OUTPUT:
3
1
4
For the first test case, the minimum imbalance is 3. One way to achieve imbalance 3 is to set [s1,s2,s3]=[4,1,7].
SAMPLE INPUT:
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
SAMPLE OUTPUT:
3
3 1 6
1
6 5 5 5 5
4
5 1 9
This input is the same as the first one aside from the value of B. Another way to achieve imbalance 3 is to set [s1,s2,s3]=[3,1,6].
SCORING:
Test cases 3-4 satisfy li=ri for all i.
Test cases 5-6 satisfy pi=i−1 for all i.
Test cases 7-16 satisfy no additional constraints.
Within each subtask, the first half of the test cases will satisfy B=0, and the rest will satisfy B=1.
Problem credits: Andrew Wang