Tree Coloring

You are given a tree with n vertices. Each vertex must be colored with one of the colors numbered from 1 to n. Coloring one vertex with color i costs i.

Any two vertices directly connected by an edge must have different colors. Find the minimum possible total cost to color every vertex while satisfying this condition.

The first line contains n, the number of vertices and also the number of available colors. (1 ≤ n ≤ 100,000)

Each of the next n - 1 lines contains two vertices u and v that are connected by an edge in the tree.

Print the minimum total cost needed to color all vertices validly.