매칭

무방향 그래프에서 매칭(matching)이란 간선들의 부분집합으로, 각 정점이 선택된 간선 중 최대 하나에만 인접하도록 고른 것입니다. 최대 매칭(maximum matching)은 포함된 간선의 수가 가능한 한 큰 매칭을 뜻합니다.

정점이 $n$개인 트리가 주어집니다. 이 트리의 최대 매칭의 크기와, 최대 매칭의 개수를 구하세요. 단, 개수는 $m$으로 나눈 나머지를 출력합니다.

첫째 줄에 트리의 정점 수를 나타내는 정수 $n$이 주어집니다 ($1 \le n \le 1\,500\,000$). 정점은 $1$번부터 $n$번까지 번호가 매겨져 있습니다.

이어지는 $n-1$개의 줄에는 트리의 간선이 한 개씩 주어집니다. 각 줄에는 두 정수 $a$와 $b$가 주어지며, 이는 정점 $a$와 정점 $b$를 잇는 간선을 의미합니다 ($1 \le a, b \le n$).

마지막 줄에는 정수 $m$이 주어집니다 ($1 \le m \le 10^9$).

첫째 줄에 트리의 최대 매칭의 크기를 출력합니다.

둘째 줄에 최대 매칭의 개수를 $m$으로 나눈 나머지를 출력합니다.