Counting Valid Correspondences in a Damaged Star Ornament

Little Y loves to create ornaments by connecting small stars with colorful threads. Originally, she had (n) stars connected by (m) threads (each thread connects two distinct stars). One day, her ornament was damaged and only (n-1) threads remain; these threads still connect all the stars forming a tree. She has her original design drawing and now wonders: In how many ways can one assign every star of the damaged ornament to a star in the original design such that if two stars in the damaged ornament are connected by a thread, then the corresponding stars in the original design are also connected by a thread? Your task is to compute the number of such bijections (one-to-one correspondences).

inputFormat

The first line contains two integers (n) and (m) (number of stars and number of threads in the original design). The next (m) lines each contain two integers (u) and (v) ((1 \le u,v \le n)), denoting an undirected edge in the original design. Then follow (n-1) lines, each containing two integers (u) and (v), denoting an edge in the damaged ornament (which forms a tree). It is guaranteed that the damaged ornament is connected and has (n) stars.

outputFormat

Output a single integer representing the number of valid bijections such that for every edge ((u,v)) in the damaged ornament, the images ((f(u), f(v))) are connected by an edge in the original design.

sample

3 3
1 2
2 3
1 3
1 2
2 3

6