Cân Bằng Cây

Farmer John có một cây có gốc với $N$ đỉnh ($2\le N\le {10}^5$). Mỗi đỉnh $i$ có cha là $p_i$ và cần được gán một giá trị nguyên $s_i\in [l_i,r_i]$.

"Độ mất cân bằng" được định nghĩa là hiệu tuyệt đối lớn nhất $|s_i-s_j|$ giữa bất kỳ đỉnh $i$ và tổ tiên $j$ của nó.

Hãy gán giá trị cho các đỉnh sao cho độ mất cân bằng là nhỏ nhất.

Dữ liệu vào

• Dòng 1: Hai số nguyên $T$ (số test case) và $B\in \{0,1\}$
• Với mỗi test case:
  • Dòng 1: Số nguyên $N$
  • Dòng 2: $N-1$ số nguyên $p_2,p_3,\dots ,p_N$
  • $N$ dòng tiếp theo: Hai số nguyên $l_i$ và $r_i$ cho mỗi đỉnh

Dữ liệu ra

Với mỗi test case:

• Dòng 1: Độ mất cân bằng tối thiểu
• Nếu $B=1$: Dòng 2 gồm $N$ số nguyên — một cách gán hợp lệ

Ràng buộc

• $1\le T\le 10$
• Tổng $N$ qua tất cả test case $\le {10}^5$
• $0\le l_i\le r_i\le {10}^9$
• Test 1-5: $B=0$
• Test 6-16: $B=1$

Ví dụ