[ONTAK2010]Matchings

时间限制:20s      空间限制:32MB

题目描述

给定一棵树,求他的最大匹配和最大匹配的方案数(mod m)。


输入格式

第一行一个整数N,表示节点个数。
接下来N-1行每行两个数x y,表示这棵树的一条边。
最后一行一个整数M,表示模数。


输出格式


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


样例输入

5
1 2
3 2
4 5
1 4
17


样例输出

2
3


提示

【数据范围】
N<=15*10^5,M<=10^9。


题目来源

By Sbullet