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$). Đỉnh $1$ là gốc, đỉnh $i\ge 2$ có cha là $p_i$ với $p_i<i$. Mỗi đỉnh $i$ 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 $s_1,s_2,\dots ,s_N$, là một cách gán đạt được độ mất cân bằng đó

Giá trị $B$ giống nhau cho mọi test case trong cùng một bộ dữ liệu. Cách gán thường không duy nhất, mọi cách gán hợp lệ đều được chấp nhận.

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$

Ví dụ