Фермер Джон вивчає еволюцію порід корів. Результат - кореневе дерево з \(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\) називається предком вершини \(i\), якщо \(j=p_i\) або \(j\) предок вершини \(p_i\).

Кожна вершина \(i\) у цьому дереві асоціюється з породою, що має ціле число плям \(s_i\). Дисбалансом такого дерева називається максимум \(|s_i-s_j|\) по всіх парах \((i,j)\) таким, що \(j\) є предок \(i\).

Фермер Джон не знає точне значення \(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\) містять призначення кількості плям для досягнення вищевказаного дисбалансу. Будь-яке правильне призначення буде прийняте.

Приклад вхідних даних

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\). Один із способів його отримати \([s_1,s_2,s_3]=[4,1,7]\).

Приклад вхідних даних

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

Це введення аналогічне вводу першого тесту крім значення \(B\) Інший спосіб досягти дисбалансу \(3\), \([s_1,s_2,s_3]=[3,1,6]\).

ОЦІНЮВАННЯ:

• У тестах 3-4 \(l_i=r_i\) для всіх \(i\).
• У тестах 5-6 \(p_i=i-1\) для всіх \(i\).
• в тестах 7-16 немає додаткових обмежень.

Всередині кожної підзадачі перша половина тестів матиме \(B=0\), друга - \( B = 1 \).