Description

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.

Input Format

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 Format

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

7
1 3 2 4 7
2 1 3
4 1 6
3 0
7 1 5
5 0
6 0

3
4

Hint

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

Translated by ChatGPT 5