Farmer John has conducted an extensive study of the evolution of different cow breeds. The result is a rooted tree with NN (2≤N≤1052≤N≤105) nodes labeled 1…N1…N, each node corresponding to a cow breed. For each i∈**[2,N]i∈[2,N], the parent of node ii is node pipi (1≤pi<**i1≤pi<i), meaning that breed ii evolved from breed pipi. A node jj is called an ancestor of node ii if j=pij=pi or jj is an ancestor of pipi.

Every node ii in the tree is associated with a breed having an integer number of spots sisi. The "imbalance" of the tree is defined to be the maximum of |si−sj**|**|si−sj| over all pairs of nodes (i,j)(i,j) such that jj is an ancestor of ii.

Farmer John doesn't know the exact value of sisi 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**]si∈[li,ri] (0≤li≤ri≤1090≤li≤ri≤109) to each node such that the imbalance of the tree is minimized.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains TT (1≤T≤101≤T≤10), the number of independent test cases to be solved, and an integer B∈**{0,1}B∈{0,1}.Each test case starts with a line containing NN, followed by N−1N−1 integers p2,p3**,…,pNp2,p3,…,pN.

The next NN lines each contain two integers lili and riri.

It is guaranteed that the sum of NN over all test cases does not exceed 105105.

OUTPUT FORMAT (print output to the terminal / stdout):

For each test case, output one or two lines, depending on the value of BB.The first line for each test case should contain the minimum imbalance.

If B=1,B=1, then print an additional line with NN space-separated integers s1**,s2**,…,sNs1,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 33. One way to achieve imbalance 33 is to set [s1,s2**,s3**]=[4,1,7][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 BB. Another way to achieve imbalance 33 is to set [s1,s2**,s3**]=[3,1,6][s1,s2,s3]=[3,1,6].

SCORING:

• Test cases 3-4 satisfy li**=ri**li=ri for all ii.
• Test cases 5-6 satisfy pi**=i−**1pi=i−1 for all ii.
• Test cases 7-16 satisfy no additional constraints.

Within each subtask, the first half of the test cases will satisfy B=0B=0, and the rest will satisfy B=1B=1.