The Mayo Empire

In the history of Asia there was an ancient empire called Mayo, one of the strongest countries of its time. At first the empire consisted of a single city, which was also the capital. Its people were great warriors, so they began to invade their neighbors and enlarge their lands.

Every time they defeated a neighbor, they razed all of that country's cities except the biggest one and added the surviving city to the empire. They also built a road from that city to one of their own cities, so that people could travel between every city of Mayo. If the added city was big enough, it became the new capital of Mayo.

The vulnerability of a city in Mayo is the number of roads one has to pass to travel from that city to the capital of Mayo. You are given the list of every kingdom that the people of Mayo invaded and the description of the roads they built.

We want to know the maximum vulnerability among the cities after each city was added to Mayo. To keep the output short, report $v_1 + v_2 + \dots + v_n$, where $v_i$ is the maximum vulnerability of the cities right after the $i$-th city was added.

The input contains several test cases.

The first line of each test case contains $n$ ($1 \le n \le 100\,000$), the number of cities in Mayo. The cities are numbered from $1$ to $n$ in the order they were added to Mayo, so city $1$ is the first city of Mayo and its initial capital.

The $i$-th of the next $n - 1$ lines contains two integers $j$ and $c$. It means that when city $i + 1$ was added to Mayo, a road was built between city $i + 1$ and city $j$, which already belonged to Mayo. The number $c$ is non-zero if city $i + 1$ became the new capital of Mayo at the time it joined, and zero otherwise.

The last line of the input contains a single 0.

For each test case, print one line containing the sum of the maximum vulnerabilities described in the statement.