In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you are familiar with IRC chat, the support team is also reachable on PIRC network (irc.pirc.pl
) in #szkopul
channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
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 .
For the input data:
5 1 2 3 2 4 5 1 4 17
the correct result is:
2 3
Task author: Tomasz Idziaszek.