题目描述

给定一棵树，求他的最大匹配和最大匹配的方案数模 $m$ 的结果。

输入格式

第一行一个整数 $n$，表示节点个数。

接下来 $n - 1$ 行每行两个数 $x$，$y$，表示这棵树的一条边。

最后一行一个整数 $m$，表示模数。

输出格式

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

5
1 2
3 2
4 5
1 4
17

2
3

提示

$n \le 1.5 \times 10^6,~m \le 10^9$

题目来源

By Sbullet