Fişkalar

Ağac tipli qrafa baxaq. Bu ağacın hər bir buğumunda(kəsişmə nöqtəsində) bir və ya bir neçə fişka yerləşdirmək olar. Fişkaları yerləşdirdikdən sonra ağacın elə kəsişmə nöqtələrini seçmək olar ki, onda iki və daha çox fişka var. Onlardan iki fişka götürüb yerinə ixtiyari qonşu kəsişmə nöqtəsindən bir fişka qoyuruq. Bu əməliyyatı bir neçə dəfə təkrarlamaq olar. Sizin tapşırıq elə fişkaların ən böyük sayını(mütləq qiymətcə M-i aşmayan) tapmaqdır ki, onları ağacda elə yerləşdirmək olur ki, aşağıdakı şərt ödənilir: ağacda göstərilən əməliyyat ilə heç bir fişka yerləşdirmək mümkün olmayan heç olmazsa bir kəsişmə nöqtəsi tapılır.

Giriş verilənləri

Girişin birinci sətrində testlərin T (1 ≤ T ≤100) sayı yerləşir. Sonrakı T sayda testin hər birində iki ədəd: ağacdakı kəsişmə nöqtələrinin N (2 ≤ N ≤ 30000) sayı və M (2 ≤ M ≤ 2³¹–1) ədədi yerləşir.

Daha sonra aralarında boşluq işarəsi olmaqla ağacda iki qonşu olan kəsişmə nöqtələrinin nömrələri (kəsişmə nöqtələri 1-dən N-dək nömrələnmişdir)yerləşən N-1 sayda sətir gəlir.

Çıxış verilənləri:

T sayda sətrin hər birini "Case #A: B" şəklində verin. Burada A testin nömrəsi(1-dən başlayaraq), B verilmiş test üçün axtarılan kəmiyyətdir.