In the event of technical difficulties with Szkopuł, please contact us via email at firstname.lastname@example.org.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#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:
Task author: Tomasz Idziaszek.