In an undirected graph, a matching is a subset of the edges of the graph such that
each vertex of the graph is adjacent to at most one of the selected edges.
The maximum matching is a matching of maximum possible cardinality.
You are given a tree with nodes.
Your task is to find the size of the maximum matching and the number of maximum matchings
(the latter one modulo ).
The first line of input contains an integer
that denotes the number of nodes of the tree ().
The nodes are numbered through .
The following lines contain a description of the tree edges.
Each of the lines contains two integers
and that represent an edge connecting the nodes and
The last line of input contains an integer ().
The first line of output should contain the cardinality of the maximum
matching in the tree.
The second line should contain the number of maximum matchings modulo .