Little Y is a clever girl who enjoys making small ornaments by hand. She has $n$ small stars, which she connected using $m$ colored threads, with each thread connecting two small stars. One day, she discovered that her ornament had been damaged, and many threads had been removed. Only $n-1$ threads remained in the ornament, but these stars were still connected by these threads, meaning the stars formed a tree.

Little Y found the original design blueprint for the ornament and wants to know which small stars in the current ornament correspond to which small stars on the original blueprint. If two small stars in the current ornament are connected by a thread, then the corresponding small stars on the original blueprint must also be connected by a thread.

Little Y wants to know how many possible ways there are to establish this correspondence. Only if you provide her with the correct answer will she give you the small ornament as a gift.

Input

The first line contains two positive integers $n$ and $m$, representing the number of small stars and the number of threads in the original ornament, respectively.

The next $m$ lines each contain two positive integers $u, v$, representing that the small stars $u$ and $v$ in the original ornament are connected by a thread. Here, the small stars are numbered starting from 1. It is guaranteed that $u \neq v$, and there is at most one thread between any pair of small stars.

The next $n-1$ lines each contain two positive integers $u, v$, representing that the small stars $u$ and $v$ in the current ornament are connected by a thread. It is guaranteed that these small stars are connected by the threads to form a tree.

Output

Output a single integer representing the number of possible ways to establish the correspondence. If no valid correspondence exists, output 0.

Examples

Input 1

4 3
1 2
1 3
1 4
4 1
4 2
4 3

Output 1

6

Note 1

In the current ornament, the 4th small star corresponds to the 1st small star in the original, and the 1st, 2nd, and 3rd small stars in the current ornament can correspond to the 2nd, 3rd, and 4th small stars in the original, so there are 6 possible ways.