P1623 [CEOI 2007] Tree Matching Treasury

Given a tree, you may match two vertices that are connected by an edge. Find the size of a maximum matching of this tree, and compute how many maximum matchings there are.

The first line contains an integer $N$, the number of nodes. Each of the next $N$ lines describes one node: the first integer is the ID of the node being described, then an integer $m$ indicating that this node has $m$ children, followed by $m$ integers, the IDs of its $m$ children.

Output two lines: the first line is the size of the maximum matching, and the second line is the number of maximum matchings.

Constraints: $1\leq N\leq 10^3$. For 40% of the testdata, the answer does not exceed $10^8$. Translated by ChatGPT 5