Matchings

In an undirected graph, a matching is a subset of the edges such that every vertex is incident to at most one selected edge. A maximum matching is a matching that contains as many edges as possible.

You are given a tree with $n$ nodes. Find the size of its maximum matching and the number of maximum matchings. The count must be reported modulo $m$.

The first line contains an integer $n$, the number of nodes in the tree ($1 \le n \le 1\,500\,000$). The nodes are numbered from $1$ to $n$.

Each of the next $n-1$ lines describes one edge of the tree with two integers $a$ and $b$, meaning there is an edge connecting nodes $a$ and $b$ ($1 \le a, b \le n$).

The last line contains an integer $m$ ($1 \le m \le 10^9$).

On the first line, print the size of a maximum matching of the tree.

On the second line, print the number of maximum matchings modulo $m$.