시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 24 6 4 20.000%

## 문제

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 ≤ 109).

## 출력

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.

## 예제 입력 1

5
1 2
3 2
4 5
1 4
17


## 예제 출력 1

2
3