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