트리 균형 맞추기

농부 존은 여러 소 품종의 진화를 깊이 연구해 왔다. 그 결과는 $N$개 ($2\le N\le 10^5$)의 노드로 이루어진 루트 달린 트리이며, 노드에는 $1\ldots N$번 번호가 붙어 있고 각 노드는 소 품종 하나에 대응한다. 각 $i\in [2,N]$에 대해 노드 $i$의 부모는 노드 $p_i$ ($1\le p_i < i$)이며, 이는 품종 $i$가 품종 $p_i$에서 진화했다는 뜻이다. 노드 $j$는 $j=p_i$이거나 $j$가 $p_i$의 조상이면 노드 $i$의 조상이라고 한다. 트리의 모든 노드 $i$에는 반점 수 $s_i$(정수)를 가진 품종이 대응한다. 트리의 불균형도는 $j$가 $i$의 조상인 모든 노드 쌍 $(i,j)$에 대한 $|s_i-s_j|$의 최댓값으로 정의한다. 농부 존은 각 품종의 $s_i$ 정확한 값은 모르지만 그 하한과 상한은 알고 있다. 여러분의 과제는 각 노드에 정수 $s_i\in[l_i,r_i]$ ($0\le l_i\le r_i\le 10^9$)를 배정하여 트리의 불균형도를 최소화하는 것이다.

첫 줄에는 테스트케이스의 수 $T$ ($1\le T\le 10$)와 정수 $B\in\{0,1\}$이 주어진다. 각 테스트케이스는 $N$이 적힌 줄로 시작하고, 이어서 $N-1$개의 정수 $p_2,p_3,\ldots,p_N$이 적힌 줄이 주어진다. 다음 $N$개 줄에는 각각 두 정수 $l_i$와 $r_i$가 주어진다. 모든 테스트케이스의 $N$을 합하면 $10^5$를 넘지 않는다고 보장된다.

각 테스트케이스마다 $B$의 값에 따라 한 줄 또는 두 줄을 출력한다. 첫 줄에는 최소 불균형도를 출력한다. $B=1$이면 위의 불균형도를 달성하는 배정 $s_1,s_2,\ldots,s_N$을 공백으로 구분해 한 줄 더 출력한다. 올바른 배정이라면 어떤 것이든 받아들여진다.