Chocolate Bar - Revolution
Akim has won a gold medal at the IOI, and as a reward, he is eligible to receive a chocolate bar from the government. There are N different types of chocolate bars made by the state chocolate factory, each with its own cost. Every type, except for the "Yulka" chocolate bar, has a predecessor type. A predecessor can only be a chocolate bar that was introduced earlier. Historically, the first type is "Yulka".
Akim and an official are tasked with selecting a chocolate bar for Akim. Akim wants the most expensive chocolate bar, while the official aims to minimize the cost. The selection process begins with "Yulka". On his turn, Akim can either take the current chocolate bar or switch to a descendant chocolate bar, if available. The official, believing that newer types are inferior and cheaper, will switch to a descendant chocolate bar if possible, or otherwise, he will purchase the current chocolate bar for Akim. Akim makes the first move.
Your task is to determine the cost of the chocolate bar that Akim will ultimately receive.
Input
The chocolate bar types are numbered in an arbitrary order, with "Yulka" being number 1. The first line of the input contains a single integer N - the number of chocolate bar types (0 < N ≤ 200000). The following N lines each contain 2 integers P_i and C_i - the predecessor type number of the i-th type and the cost of the i-th type (0 ≤ P_i ≤ N, 0 < C_i ≤ 1000000000; for "Yulka", which has no predecessor, P_1 = 0 is specified).
Output
Output a single integer - the cost of the chocolate bar that Akim will receive, assuming both he and the official make optimal choices.