题目描述

给定一棵树，求他的最大匹配和最大匹配的方案数(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。