Description

Xiao Y is a skillful girl who likes making small handmade accessories. She has $n$ little stars, strung together by $m$ colored thin threads, and each thread connects two stars.

One day she found that her accessory had been damaged, and many threads were removed. The accessory now has only $n-1$ threads, but through these threads, the stars are still strung together; that is, these stars form a tree through these threads. Xiao Y found the design blueprint and wants to know which original stars on the blueprint correspond to the current stars in the accessory. If two stars are connected by a thread in the current accessory, then the corresponding stars must also be connected by a thread on the original blueprint. Xiao Y wants to know how many possible correspondences there are.

Only if you tell her the correct answer will she give you the accessory as a gift.

Input Format

The first line contains $2$ positive integers $n, m$, representing the number of stars and the number of threads in the original accessory.

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

The next $n-1$ lines each contain $2$ positive integers $u, v$, indicating that in the current accessory, stars $u$ and $v$ are connected by a thread. It is guaranteed that these stars are connected through the threads.

Output Format

Output a single line containing one integer, the number of possible correspondences.

If no feasible correspondence exists, output 0.

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

6

Hint

For $100\%$ of the testdata, $n\leq 17$, $m\leq \frac 12n(n-1)$.

Translated by ChatGPT 5