Postman

Johnny has just become a postman. He is new to the company, so he got the worst assignment: delivering urgent mail to a new neighborhood. The delivery deadline is exactly one hour away. The postal company has also introduced a new customer-friendly rule: for each letter delivered after its deadline, the company pays compensation of $1$ bythaler for every hour of delay.

The neighborhood has $n$ houses, numbered from $1$ to $n$. Johnny has to deliver one letter to each house. The houses are connected by $n-1$ two-way streets, so any house can be reached from any other house by following the streets.

Johnny must deliver the letters as soon as possible. Due to company driving regulations, a company car takes him to one house of his choosing, and after that Johnny walks. The ride takes exactly one hour, so he delivers exactly one letter on time. Walking along a street takes exactly one hour. Dropping a letter in a mailbox takes no time. Johnny has to deliver all the letters.

Johnny knows that on-time delivery is impossible, but he still wants to minimize the total compensation the postal company pays. Write a program that reads the number of houses and the streets, computes the minimum compensation for late deliveries, and prints it.

The first line contains a single integer $n$ ($1 \le n \le 1\,000\,000$), the number of houses. Each of the next $n-1$ lines contains two integers $a$ and $b$ ($1 \le a,b \le n$), separated by a space, meaning houses $a$ and $b$ are directly connected by a street.

Print the minimum compensation in bythalers.

Johnny can be dropped off at house 1 and deliver the letter on time, so the compensation is $0$. Then he walks to house 2 and delivers the letter with compensation of $1$, then walks to house 3 and delivers with compensation of $2$. Next, he returns to house 2, walks on to house 4 and delivers there with compensation of $4$, returns to house 2 again, walks to house 5 and delivers the final letter with compensation of $6$.