В компании NAUMEN очень ценятся личные качества сотрудников. Основными личными качествами являются сила и ум. Недавно компания провела тестирование всех своих сотрудников, в результате которого были определены показатели силы и ума. По мнению исследователей, эти параметры позволят объективно оценить работоспособность каждого сотрудника.

Всего в компании $$$N$$$ сотрудников, пронумерованных от $$$1$$$ до $$$N$$$. Компания имеет иерархическую структуру. Чем меньше номер сотрудника, тем он главнее. Сотрудник номер $$$1$$$ является директором, у него нет начальника. У всех остальных сотрудников есть начальник: у сотрудника номер $$$i$$$ начальником является сотрудник номер $$$P_i$$$ ($$$P_i \lt i$$$). Также принято считать, что $$$P_1 = 0$$$.

В результате исследования было определено, что $$$i$$$-й сотрудник имеет силу $$$A_i$$$ и ум $$$B_i$$$. Эти показатели важны при решении проблем. Исследователи компании NAUMEN предложили следующую математическую модель проблемы: по их мнению, проблема — это пара натуральных чисел $$$(x, y)$$$. Первое число описывает физическую сложность проблемы, второе число — умственную. Считается, что сотрудник номер $$$i$$$ может самостоятельно решить проблему $$$(x, y)$$$, если $$$A_i \ge x$$$ и $$$B_i \ge y$$$. Таким образом, учитываются как сила, так и ум.

Конечно, сотрудники не всегда решают проблемы поодиночке. Если у сотрудника в подчинении есть люди, он может делегировать любому своему непосредственному подчинённому эту проблему. Тот сотрудник, кому проблема была делегирована, может в свою очередь делегировать её одному из своих подчинённых, и так далее. Таким образом, если хотя бы один из подчинённых $$$i$$$-го сотрудника может решить проблему, то считается, что и $$$i$$$-й сотрудник может её решить.

Вам было поручено подведение итогов исследования. Для этого нужно для каждого сотрудника посчитать, сколько различных проблем он умеет решать. Обратите внимание, что раз параметры $$$x$$$ и $$$y$$$ в любой проблеме $$$(x, y)$$$ — натуральные числа, то множество различных проблем, которые умеет решать сотрудник, всегда конечно.

$$$$$$ \begin{array} {|c|c|c|c|}

\hline \textbf{Подзадача} & \textbf{Баллы} & \textbf{Ограничения} & \textbf{Необх. подзадачи} \\ \hline 1 & 21 & N \le 5, A_i \le 10, B_i \le 10 & \\ \hline 2 & 26 & N \le 50, A_i \le 100, B_i \le 10^6 & 1 \\ \hline 3 & 23 & N \le 5000, A_i \le 100, B_i \le 10^6 & 1, 2 \\ \hline 4 & 14 & N \le 500, A_i \le 10^6, B_i \le 10^6 & 1, 2 \\ \hline 5 & 16 & N \le 50000, A_i \le 10^6, B_i \le 10^6 & 1, 2, 3, 4 \\ \hline \end{array}$$$$$$

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