Problem Description

Given a tree, assign a weight to each node. The weight can be any positive integer.

The only constraint is that two adjacent nodes cannot have the same weight. Find an assignment that minimizes the total weight of the entire tree.

Input Format

The first line contains an integer $N$ representing the number of nodes in the tree, with $N \le 10000$.

Each of the next $N-1$ lines indicates that two nodes $u,v(1\le u,v\le N)$ are connected by an edge.

Output Format

The minimum possible total weight.

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

14

Hint

Translated by ChatGPT 5