[CEOI2007]树的匹配Treasury

题目描述

给一棵树,你可以匹配有边相连的两个点,问你这棵树的最大匹配时多少,并且计算出有多少种最大匹配。

输入输出格式

输入格式


第一行一个数N,表示有多少个结点。 接下来N行,每行第一个数,表示要描述的那个结点。然后一个数m,表示这个结点有m个儿子,接下来m个数,表示它的m个儿子的编号。 【数据规模】 N≤1000,其中40%的数据答案不超过$10^8$

输出格式


输出两行,第一行输出最大匹配数,第二行输出最大匹配方案数。

输入输出样例

输入样例 #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