Problem2368--暑假提高组模拟测试卷四 T3 树的世界

2368: 暑假提高组模拟测试卷四 T3 树的世界

Time Limit: 1.000 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:][下载测试数据]

Description

小 A 最近沉迷 「我的世界」这款游戏,他喜欢在里面搭建各种建筑群。这一次,他要建立一个梦幻般的庄园,庄园总共有 n 个建筑和 n-1 条路,我们可以把建筑看成点,路看成边。形式化地说,这个庄园中的建筑和路形成了一棵 n 个结点的无根树,结点编号为 1,2,.......,n。

现在,小 A 想要对这些路进行改造,他想要在其中一些路上铺上花哨的多彩大理石。小 A 非常喜欢这种大理石路面,所以他想要铺上大理石的路越多越好。同时,小 A 又是艺术的,他不希望出现有两条铺了大理石的路连接同一个建筑,这样会变得不美观。

简单来说,小 A 想要在庄园这棵无根树中,选择最多的边,使得这些边没有公共顶点。

现在,小 A 想要知道能够铺上大理石的最多的路的数量,并且在满足数量最多的前提下,这样的铺法有多少种。



Input

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

接下来 n 行,每行第一个整数,表示需要描述的建筑结点。接下来会输入一个整数 m,表示这个结点有 m 个儿子,接下来 m 个整数,表示它的 m 个儿子的编号。



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

HINT

【样例解释】

样例构成的树,假设 1为根,那么如下所示


我们选择的最大的路径数量为 3,其中路径选择方案有 {a,e,f},{b,d,f},{c,d,e},{d,e,f},共 4 种方案。

【数据范围】

对于 25% 的数据,n< 20,并且保证答案不超过 1000;

对于 60% 的数据,n < 1000,并且保证答案不超过 10^8;

对于 100% 的数据,保证 n < 1000。



Source/Category

 

[Submit] [Status]