P3349 [ZJOI2016] Little Stars

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.

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 a single line containing one integer, the number of possible correspondences. If no feasible correspondence exists, output `0`.

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