DMOPC '21 Contest 2 P5 - Permutations

View as PDF

Points: 25 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

You are given a tree with nodes, the -th node initially having a value of . In one operation, you may remove any edge from the tree after swapping the values of the two nodes it connects. How many possible permutations of values are there after performing exactly operations?

Input Specification

The first line contains integers and .

The next lines each contain integers and , denoting the endpoints of the -th edge.

Output Specification

Output the number of possible permutations of values after performing exactly operations. Since this value may be large, output it modulo .

Sample Input 1

4 2
1 2
3 1
2 4

Sample Output 1

5

Explanation for Sample 1

The five possible permutations are listed below as arrays, where the -th element represents the value of the -th node:

Sample Input 2

20 15
9 3
2 4
10 20
1 19
7 20
15 16
11 19
17 16
5 19
16 20
4 17
13 11
6 20
14 17
12 19
18 19
8 3
19 16
3 15

Sample Output 2

315531008