Description

When it rains, puddles form on the ground. Each puddle flows to exactly one specific other puddle, and the flow is one-way (no backflow). Multiple puddles may flow into the same puddle. On this day, it started to rain "mixed with ducks", and there is a duck floating in every puddle. WYH dispatches an agent beside every puddle, and each agent marks the duck in his puddle. At a certain moment, all ducks start drifting along with the water simultaneously, and all agents start timing. When an agent sees the duck he marked drift back, he stops timing and reports the time to WYH. After surveying the terrain, WYH tells you the flow relation and travel time for every segment, and he wants to know the maximum among all the numbers he obtained.

Input Format

The first line contains a positive integer $n$, meaning there are $n$ puddles (numbered from $1$ to $n$).

Lines $2 \sim n+1$ each contain two positive integers. On line $i+1$, the two integers are $D_i$ and $T_i$, meaning the water of puddle $i$ flows to puddle $D_i$, and the flow takes time $T_i$. It is guaranteed that $D_i \neq i$.

Output Format

Output a single integer, the maximum among the agent-reported times that WYH has.

6
2 1
3 2
1 3
5 2
6 2
4 2

6

Hint

For $30\%$ of the testdata, $n \leq 100$.

For $100\%$ of the testdata, $n \leq 10^5$.

Translated by ChatGPT 5