Задача 8. Повышение квалификации

Автор:Центральная предметно-методическая комиссия   Ограничение времени:1 сек
Входной файл:qual.in   Ограничение памяти:256 Мб
Выходной файл:qual.out  
Максимальный балл:100  

Условие

Взаимодействие сотрудников в некоторой компании организовано в виде иерархической структуры. Всего в компании работают n сотрудников. Каждому сотруднику присвоен уникальный номер от 1 до n, директору присвоен номер 1. У каждого сотрудника, кроме директора, есть ровно один непосредственный начальник. Непосредственный начальник сотрудника i имеет номер pi , причем pi < i.

Сотрудник x является подчиненным уровня 1 сотрудника y, если px = y. Для k > 1 сотрудник x является подчиненным уровня k сотрудника y, если сотрудник px является подчиненным уровня k − 1 сотрудника y.

У директора компании появилась возможность направить некоторых сотрудников на курсы повышения квалификации. Для этого он решил выбрать два числа L и R и направить на курсы всех сотрудников с номерами i, такими что L ≤ i ≤ R.

Перед тем, как выбрать числа L и R, директор получил m пожеланий от сотрудников компании, j-е пожелание задается двумя числами uj и kj и означает, что сотрудник uj просит отправить на курсы одного из своих подчиненных уровня kj. Для экономии средств директор хочет выбрать такие L и R, чтобы количество сотрудников, направленных на повышение квалификации, было минимальным возможным, но при этом все пожелания были выполнены.

Требуется написать программу, которая по заданным в компании отношениям начальник-подчиненный и пожеланиям сотрудников определяет такие числа L и R, что если отправить на курсы повышения квалификации всех сотрудников с номерами от L до R включительно, то все пожелания будут выполнены, а количество сотрудников, направленных на повышение квалификации, будет минимальным возможным. Если оптимальных пар чисел L, R будет несколько, требуется найти ту из них, в которой значение L минимально.

Формат входного файла

Первая строка входного файла содержит число n — количество сотрудников компании. Вторая строка содержит (n − 1) чисел: p2, p3, …, pn (1 ≤ pi ≤ i) — номера непосредственных начальников сотрудников.

Третья строка содержит число m — количество пожеланий от сотрудников.

Последующие m строк задают пожелания сотрудников и содержат по два целых числа uj, kj (1 ≤ uj < n, 1 ≤ kj < n, гарантируется, что у сотрудника uj есть хотя бы один подчиненный уровня kj).

Формат выходного файла

Необходимо вывести два искомых числа: L и R. Если оптимальных пар (L, R) несколько, требуется вывести ту, в которой значение L минимально.

Ограничения

2 ≤ n, m ≤ 200 000

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

Подзадача Баллы Ограничения Необходимые подзадачи
nДополнительные условия
1192 ≤ n, m ≤ 50
2252 ≤ n, m ≤ 3000 1
3212 ≤ n, m ≤ 200 000для всех i выполнено pi = i − 1
4352 ≤ n, m ≤ 200 000 1, 2, 3

Получение информации о результатах окончательной проверки

По запросу сообщаются баллы за каждую подзадачу.

Пояснение к примеру

На повышение квалификации будут направлены сотрудники с номерами 3, 4, 5 и 6. Сотрудник с номером 3 является подчиненным уровня 1 сотрудника с номером 1, сотрудник с номером 4 — подчиненным уровня 2 сотрудника с номером 1, а сотрудник с номером 6 — подчиненным уровня 1 сотрудника с номером 3.

Примеры тестов

Входной файл (qual.in) Выходной файл (qual.out)
1
7
1 1 2 2 3 3
3
1 1
3 1
1 2
3 6

0.274s 0.019s 13