Фермер Джон изучает эволюцию пород коров.
Результат - корневое дерево с \(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\)) каждой вершине так, чтобы минимизировать
дисбаланс этого дерева.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(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\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Для каждого подтеста выведите одну или две строки в зависимости от значения
\(B\).
Первая строка должна содержать минимальный дисбаланс.
Если \(B=1,\) выведите дополнительную строку с разделёнными одиночными пробелами целыми числами
\(s_1,s_2,\ldots, s_N\) содержащими назначения количеств пятен для достижения вышеуказанного
дисбаланса. Любое правильное назначение будет принято.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|