Description

There is a tree with $n$ nodes. Assign a positive integer label to each node so that adjacent nodes have different labels, and the total sum of labels is as small as possible.

Input Format

The first line contains an integer $n$.

The following $n-1$ lines each contain two integers $u, v \ (1\le u, v\le n)$, indicating that there is an edge between $u$ and $v$.

Output Format

Only one line, the minimum possible sum of labels.

8  
1 2 
1 3
1 4
1 5
5 6
5 7
5 8

11

Hint

For $20\%$ of the testdata, $n\le 10$.

For $40\%$ of the testdata, $n\le 1000$.

For $100\%$ of the testdata, $1\le n\le 50000$.

Translated by ChatGPT 5