同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

22052_Tree

2022-5-16 18:21| 发布者: Hocassian| 查看: 23| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-4-8950671154500-Problem List-采集的数据-后羿采集器.html

Pro.ID

22052

Title

Tree

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=22052

AC

Submit

Ratio

0.00%

时间&空间限制

Time Limit: 1000/500 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)

描述

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

输入

第一行一个数N，表示有多少个节点。

接下来N行，每行第一个数，表示要描述的那个节点。然后一个数m，表示这个节点有m个儿子，接下来m个数，表示它的m个儿子的编号。

N ≤ 1000

输出

Description

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

Input

第一行一个数N，表示有多少个节点。

接下来N行，每行第一个数，表示要描述的那个节点。然后一个数m，表示这个节点有m个儿子，接下来m个数，表示它的m个儿子的编号。

N ≤ 1000

Output

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

Sample Input

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

Sample Output

3
4

样例输入