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
).
Constraints
Subtask 1 [1%]
Subtask 2 [4%]
Subtask 3 [10%]
Subtask 4 [15%]
Subtask 5 [15%]
Subtask 6 [15%]
Subtask 7 [15%]
Subtask 8 [25%]
No additional constraints.
Input Specification
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 .
Output Specification
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 .
Sample Input
5
1 2
3 2
4 5
1 4
17
Sample Output
2
3
Comments