Minimum Sum Labeling on a Tree

You are given a tree with n nodes. Your task is to assign a positive integer label to each node such that any two adjacent nodes have different labels, and the total sum of labels is minimized. In other words, if an edge exists between nodes u and v, then the labels assigned to u and v must be different.

Hint: A tree is a bipartite graph. You can split the nodes into two sets. By assigning one set with 1 and the other with 2, and by choosing the assignment such that the larger set gets the smaller label, you can achieve the minimum sum.

Formally, if the two parts have sizes \(a\) and \(b\) with \(a+b=n\), the minimum sum is \[ \max(a,b)\times 1 + \min(a,b)\times 2. \]

For the special case when \(n = 1\), output 1.

inputFormat

The first line contains an integer n (1 ≤ n ≤ 10⁵), representing the number of nodes in the tree. The following n - 1 lines each contain two integers u and v (1 ≤ u, v ≤ n) indicating an edge between node u and node v.

outputFormat

Output a single integer, which is the minimized sum of labels assigned to all nodes.

sample

1

1