Maximum Matching on a Tree

You are given a tree with n nodes. A matching is a set of edges such that no two edges share a common vertex. In this problem, you are allowed to match two adjacent nodes (i.e. an edge in the tree).

Your task is to compute two values:

• The size of a maximum matching, i.e. the maximum number of edges that can be chosen.
• The number of different maximum matchings.
</p>

More formally, let \( T \) be a tree. Let a matching \( M \subseteq E(T) \) be a set of edges in which no two edges share a vertex. You need to find the maximum value of \(|M|\) and count the number of matchings \( M \) that achieve this maximum size.

Note: The answer for the number of matchings will fit in the range of a 64-bit integer.

inputFormat

The first line contains an integer n (\(1 \leq n \leq 10^5\)), the number of nodes in the tree. The next n - 1 lines each contain two integers u and v (1-indexed) representing an edge between nodes u and v.

outputFormat

Output two space‐separated integers: the maximum matching size and the number of maximum matchings.

sample

2
1 2

1 1