Nông dân John đã tiến hành một nghiên cứu về sự tiến hóa của các giống bò khác nhau. Kết quả là một cây có gốc với \(N(1\leq N\leq 10^5)\) nút đánh số từ \(1\) đến \(N\), mỗi nút tương ứng với một giống bò. Với mỗi \(i∈[2,N]\), nút cha của \(i\) là nút \(p_i\) \((1\leq p_i <i)\), nghĩa là giống \(i\) tiến hóa từ giống \(p_i\). Nút \(j\) được gọi là tổ tiên của nút \(i\) nếu \(j=p_i\) hoặc \(j\) là tổ tiên của \(p_i\).

Mỗi nút \(i\) tương ứng với giống bò được gán số nguyên \(s_i\). Sự "mất cân bằng" của cây là giá trị lớn nhất của \(|s_i−s_j|\) trên tất cả các cặp nút \((i,j)\) với \(j\) là tổ tiên của \(i\).

Nông dân John không biết giá trị chính xác của \(s_i\) của mỗi giống, nhưng ông biết giới hạn dưới và giới hạn trên của những giá trị này. Công việc của bạn là gán giá trị nguyên của \(s_i∈[l_i,r_i]\) \((0 \leq l_i \leq r_i \leq 10^9)\) cho mỗi nút sao cho sự mất cân bằng của cây là nhỏ nhất.

Input

• Dòng đầu tiên chứa số \(T(1\leq T \leq 10)\) - số lượng test con, và số nguyên \(B \in (0,1)\).

• Dòng đầu tiên của mỗi test chứa số \(N\), sau đó là \(N-1\) số nguyên \(p_1,...p_N\).

• \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l_i,r_i\).

• Dữ liệu đảm bảo tổng \(N\) của tất cả các test không vượt quá \(10^5\).

Output

Với mỗi test, in ra \(1\) hoặc \(2\) dòng, dựa vào giá trị của \(B\):

• Dòng đầu in ra độ mất cân bằng nhỏ nhất.
• Nếu \(B=1\), dòng thứ \(2\) in ra \(N\) số nguyên \(s_1,...,s_N\) cách nhau bởi dấu cách.

Scoring

• Subtask \(1\): \(l_i=r_i\) với mọi \(i\).
• Subtask \(2\): \(p_i=i-1\) với mọi \(i\).
• Subtask \(3\): Không có điều kiện gì thêm.

Với mỗi subtask, nửa đầu sẽ có \(B=0\), nửa sau sẽ có \(B=1\).

Example

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

3
1
4        

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

3
3 1 6
1
6 5 5 5 5
4
5 1 9