Фішки
Розглянемо граф-дерево. У кожний вузол цього дерева можна помістити одну або декілька фішок. Після розміщення фішок можна вибрати вузол дерева, в якому є дві або більше фішок, і забрати з нього дві фішки, при цьому помістивши одну фішку в довільний з сусідніх вузлів. Таку операцію можна повторювати декілька разів. Ваша задача знайти максимальну кількість фішок (за модулем M), яку можна розмістити на дереві так, щоб виконувалась умова: знайдеться хоча б один вузол дерева, в який буде неможливо помістити жодної фішки за допомогою вказаних операцій.
Вхідні дані
У першому рядку міститься кількість тестів T (1 ≤ T ≤ 100).
Перший рядок кожного тесту містить два числа: N (2 ≤ N ≤ 30000) – кількість вузлів у дереві та M (2 ≤ M ≤ 2^31–1). Далі йде N–1 рядків, кожен з яких містить номери двох суміжних вузлів дерева (вузли пронумеровані від 1 до N), відокремлені пропуском.
Вихідні дані
Виведіть T рядків вигляду "Case #A: B", де A – номер тесту (починаючи з 1), B – шукана величина для даного тесту.