logo AlgoBeat OnlineJudge
登录 注册

#200614. [CEOI 2007] 树的匹配 Treasury

内存限制:31 MiB 时间限制:500 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

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

输入格式

第一行一个整数 ,表示有多少个结点。

接下来 行,每行第一个整数,表示要描述的那个结点。然后一个整数 ,表示这个结点有 个儿子,接下来 个整数,表示它的 个儿子的编号。

输出格式

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

样例

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

数据范围与提示

,其中 的数据答案不超过