D. Модон дахь зай

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 512 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Мод бол ямар ч цикл агуулаагүй холбогдсон граф юм.

Модны хоёр оройн хоорондох зай нь эдгээр оройнуудын хоорондох хамгийн богино замын урт (ирмэгүүдийн тоо) байна.

Танд $n$ оройтой мод ба эерэг тоо $k$ өгөгдсөн. Хоорондоо яг $k$ зайтай ялгаатай хос оройнуудын тоог ол. ($v$, $u$) ба ($u$, $v$) оройнууд адилханд тооцогдоно.

Оролт

Эхний мөрөнд хоёр бүхэл тоон утга $n$ ба $k$ ($1 ≤ n ≤ 50000$, $1 ≤ k ≤ 500$) байх ба оройнуудын тоо болон оройнуудын хоорондох шаардлагатай зай байна.

Дараагийн $n - 1$ мөрөнд ирмэгүүд "$a_{i}$ $b_{i}$" (хашилтгүйгээр) ($1 ≤ a_{i}, b_{i} ≤ n$, $a_{i} ≠ b_{i}$) хэлбэртэй байх ба энд $a_{i}$ болон $b_{i}$ нь $i$-р ирмэгээр холбогдсон оройнууд байна. Өгөгдсөн бүх ирмэгүүд ялгаатай байна.

Гаралт

Модны хоорондоо яг $k$ зайтай ялгаатай хос оройнуудын тоо болох нэг бүхэл тоон утгыг хэвлэ.

C++ хэлэнд 64 битийн бүхэл тоон утгуудыг унших эсвэл бичихдээ $\%lld$ тодорхойлогчийг битгий ашиглаарай. Харин $cin$, $cout$ урсгалууд эсвэл $\%I64d$ тодорхойлогчийг ашиглахыг зөвлөж байна.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
5 2
1 2
2 3
3 4
2 5
Гаралт
4
Оролт
5 3
1 2
2 3
3 4
4 5
Гаралт
2

Тэмдэглэл

Эхний жишээн дээр хоорондоо 2 зайтай оройнуудын хосууд нь (1, 3), (1, 5), (3, 5) ба (2, 4) байна.

Сэтгэгдлүүдийг ачааллаж байна...