Cow Telephone Network Communication

The cows have built a telephone network which can be modeled as an unrooted tree with \(N\) nodes \( (1 \le N \le 100{,}000)\) numbered from \(1\) to \(N\). Each node represents a telephone exchange and each edge represents a telephone line connecting two exchanges. The \(i\)th edge connects nodes \(A_i\) and \(B_i\) (\(1 \le A_i, B_i \le N,\) and \(A_i \ne B_i\)).

Some exchanges are connected by only one telephone line; these are the leaf nodes of the tree, and each leaf has a telephone booth in the cow field with one cow. When two cows have a conversation, the dialogue is transmitted along the unique shortest path between the two nodes. Each exchange (node) can process at most \(K\) (\(1 \le K \le 10\)) conversations simultaneously, and at any moment each telephone line (edge) can carry at most one conversation. Also, each cow (leaf) may participate in at most one conversation.

Assume that every leaf node has one cow. What is the maximum number of pairs of cows that can be engaged in conversation concurrently under these constraints?

Note: If an internal (non‐leaf) node is used by several conversations (even if coming from different branches), the number of conversations passing through that node cannot exceed \(K\). Moreover, no telephone line can be shared by more than one conversation.

Hint: One natural way to solve this problem is to reduce it to a maximum disjoint paths problem in a tree with vertex capacities. By splitting each vertex into an in‐ and out–node and assigning the edge connecting them a capacity equal to \(K\) (or 1 for leaves), and by giving each original edge a capacity of 1, the problem can be solved by computing the maximum flow between a super source and a super sink connected to all leaves.

inputFormat

The first line contains two integers \(N\) and \(K\): the number of nodes in the tree and the maximum number of conversations an exchange can handle simultaneously. The following \(N-1\) lines each contain two integers \(A_i\) and \(B_i\), indicating that there is an edge between nodes \(A_i\) and \(B_i\).

Note: In the tree, nodes which are leaves (degree 1) correspond to telephone booths with one cow each.

outputFormat

Output a single integer: the maximum number of pairs of cows that can have a conversation concurrently.

sample

2 1
1 2

1