8469번 - Matchings 다국어

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 n 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 n that denotes the number of nodes of the tree (1 ≤ n ≤ 1 500 000). The nodes are numbered 1 through n. The following n-1 lines contain a description of the tree edges. Each of the lines contains two integers a and b that represent an edge connecting the nodes a and b (1 ≤ a, b ≤ n). The last line of input contains an integer m (1 ≤ m ≤ 10⁹).

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 m.