Annettuna on puu, jossa on $n$ solmua. Tehtäväsi on laskea, monessako puun polussa on tasan $k$ kaarta.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $k$: solmujen määrä ja haluttu polun pituus. Solmut on numeroitu $1,2,\ldots,n$.

Tämän jälkeen syötteessä on $n-1$ riviä, jotka kuvaavat verkon kaaret. Jokaisella rivillä on kaksi kokonaislukua $a$ ja $b$: kaari kulkee solmujen $a$ ja $b$ välillä.

Tuloste

Tulosta, montako $k$-pituista polkua puussa on.

Rajat

• $1 \le k < n \le 10^5$

Esimerkki

Syöte:

5 2
1 2
2 3
3 4
3 5

Tuloste:

4