[CEOI2007] 树的匹配 Treasury
题目描述
给一棵树,你可以匹配有边相连的两个点,问你这棵树的最大匹配是多少,并且计算出有多少种最大匹配。
输入输出格式
输入格式
第一行一个整数 $N$,表示有多少个结点。
接下来 $N$ 行,每行第一个整数,表示要描述的那个结点。然后一个整数 $m$,表示这个结点有 $m$ 个儿子,接下来 $m$ 个整数,表示它的 $m$ 个儿子的编号。
输出格式
输出两行,第一行输出最大匹配数,第二行输出最大匹配方案数。
输入输出样例
输入样例 #1
7
1 3 2 4 7
2 1 3
4 1 6
3 0
7 1 5
5 0
6 0
输出样例 #1
3
4
说明
$1\leq N\leq 10^3$,其中 $40\%$ 的数据答案不超过 $10^8$。