34524번 - Tree Decorations 서브태스크다국어

문제

Mateo recently found the perfect decorations for his Christmas tree — more trees!

Specifically, his Christmas tree is a rooted tree $T$ initially with $M$ nodes, all painted green. He has another rooted tree $D$ that he uses as a reference for his decorations. Mateo uses the following process to put on all of his decorations:

• For each node $i$ in $D,ドル he creates a copy of the subtree rooted at $i$. Let this copy be $C_i$. Then, he paints the nodes of $C_i$ red. Finally, he chooses some green node in $T$ to be the parent of the root of $C_i$ by connecting them with an edge.

After applying all the decorations, $T$ ends up containing $N$ nodes. Unfortunately, he realized that he had forgotten to record what $D$ is! To make things worse, he accidentally spilled water on $T,ドル washing off all the colour from the nodes. After all that, he labels the root of $T$ as 1ドル,ドル and then labels the rest of the nodes from 2ドル$ to $N$.

The only information he currently has is the final state of $T,ドル as well as $M$. Help him find the number of possible $D$ that he could have started with, where two possibilities are considered different if they are structurally distinct.

Rooted trees $A$ and $B$ are said to be structurally identical if and only if they have the same number of nodes $S,ドル and there is a way to label $A$’s nodes from 1ドル$ to $S$ and $B$’s nodes from 1ドル$ to $S$ such that:

• Their roots are labeled the same.
• Nodes labeled $x$ and $y$ in $A$ are connected by an edge if and only if nodes labeled $x$ and $y$ in $B$ are connected by an edge.

Otherwise, $A$ and $B$ are considered structurally distinct.

입력

The first line of input contains two space-separated integers $N$ and $M$.

The next $N − 1$ lines each contain two space-separated integers $u_i$ and $v_i$ (1ドル ≤ u_i , v_i ≤ N,ドル $u_i \ne v_i$), describing an edge in $T$ connecting nodes $u_i$ and $v_i$. Note that $T$ is rooted at node 1ドル$.

출력

Output the number of possible $D$ that he could have started with, where two possibilities are considered different if they are structurally distinct.

제한

서브태스크

노트