У компании $$$X$$$ есть $$$n$$$ сотрудников, пронумерованных от $$$1$$$ до $$$n$$$. У каждого сотрудника $$$u$$$ есть его прямой начальник $$$p_u$$$ ($$$1 \le p_u \le n$$$), кроме сотрудника $$$1$$$, у которого начальника нет. Гарантируется, что значения $$$p_i$$$ образуют дерево. Сотрудник $$$u$$$ называется ответственным за сотрудника $$$v$$$, если $$$u$$$ является прямым начальником $$$v$$$ или есть такой сотрудник $$$w$$$, что $$$w$$$ ответственен за $$$v$$$, и $$$u$$$ является прямым начальником $$$w$$$. Любой сотрудник также считается ответственным за самого себя.

Также, для каждого сотрудника $$$u$$$ мы определим его уровень $$$lv(u)$$$ следующим образом:

• $$$lv(1)=0$$$
• $$$lv(u)=lv(p_u)+1$$$ если $$$u \neq 1$$$

У компании есть $$$q$$$ возможных планов на ближайшее будущее. При чём $$$i$$$-й из них задаётся двумя числа $$$l_i$$$ и $$$r_i$$$, означающими что в этом плане принимают участие все сотрудники в отрезке $$$[l_i, r_i]$$$ и только они. Чтобы всё прошло гладко, у плана должен быть проектный менеджер, который является ответственным за всех сотрудников в этом плане. Более формально, если сотрудник $$$u$$$ выбирается как проектный менеджер $$$i$$$-го плана, то для каждого сотрудника $$$v \in [l_i, r_i]$$$, $$$u$$$ должен быть ответственен за $$$v$$$. Заметим, что при этом не обязательно $$$u$$$ сам должен находится в отрезке $$$[l_i, r_i]$$$. Также, $$$u$$$ всегда выбирается таким образом, что $$$lv(u)$$$ является максимально возможным (чем больше уровень, тем меньше компания может платить сотруднику).

До того как любой план начнёт выполняться, компания позволила JATC заглянуть в свои планы. С первого взгляда он заметил, что для каждого плана можно уменьшить количество вовлечённых в него сотрудников ровно на один без каких-либо проблем. Будучи жадной, компания спрашивает у JATC: какого же именно сотрудника надо выкинуть из плана, чтобы уровень менеджера проекта был максимально возможным? JATC уже выяснил ответ и теперь предлагает это сделать и вам.