样例下载

【问题描述】

Farmer John 的农场中的道路形成一棵树的结构，每条边是一条道路，每个节点是一个路口，一共 N 个路口，编号为 1 ~ N。

晚上的时候，奶牛们经常在道路上走来走去，由于天黑，经常会出现各种事故。

因此 John 决定安装路灯。

为了让每一个路灯发挥最大的作用，John 决定把所有路灯都安装在路口处。

如果一个路口安装了路灯，那么这个路口以及和这个路口相邻的路口均可以被照亮。两个路口相邻指的是两个路口之间有一条道路直接相连。

问：

（1）要把所有路口都照亮，John 至少需要安装多少个路灯？

（2）在满足（1）的前提下，John 有多少种不同的安装方案？方案数可能很大，你需要将其 mod P 后输出。

【输入】

第一行：包含两个整数 N, P

接下来 N-1 行，每行两个整数 u, v 表示点 u 与点 v 之间有一条边

【输出】

第一行：输出第（1）问的答案；

第二行：输出方案数 mod P

5 6
1 2
2 3
3 4
3 5

2
2

【数据范围】

10% 的数据：$N ≤ 20$

20% 的数据：$N ≤ 1000$

100% 的数据：$N ≤ 500000, 1 ≤ u, v ≤ N, 1 ≤ P ≤ 2×10^9$