Maximum Tree Matching
Problem
You are given a tree (a connected acyclic undirected graph) consisting of n vertices.
Find the size of its maximum matching (the set of pairwise nonadjacent edges).
Input:
The first line contains the number n - the number of vertices in the tree.
Next comes n-1 lines, each of which contains two numbers a
i and b
i (1 <= a
i, b
i <= n) - tree edges.
Output:
Print one number - the size of the maximum matching of the given tree.
Examples:
| Input |
Output |
4
1 2
23
3 4 |
2 |
Explanation:
The maximum matching of this tree will include edges 1-2 and 3-4.