eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Фішки

Фішки

Ліміт часу 2 секунди
Ліміт використання пам'яті 64 MiB

Розглянемо граф-дерево. У кожний вузол цього дерева можна помістити одну або декілька фішок. Після розміщення фішок можна вибрати вузол дерева, в якому є дві або більше фішок, і забрати з нього дві фішки, при цьому помістивши одну фішку в довільний з сусідніх вузлів. Таку операцію можна повторювати декілька разів. Ваша задача знайти максимальну кількість фішок (за модулем M), яку можна розмістити на дереві так, щоб виконувалась умова: знайдеться хоча б один вузол дерева, в який буде неможливо помістити жодної фішки за допомогою вказаних операцій.

Вхідні дані

У першому рядку міститься кількість тестів T (1T100).

Перший рядок кожного тесту містить два числа: N (2N30000) – кількість вузлів у дереві та M (2M2^31–1). Далі йде N1 рядків, кожен з яких містить номери двох суміжних вузлів дерева (вузли пронумеровані від 1 до N), відокремлені пропуском.

Вихідні дані

Виведіть T рядків вигляду "Case #A: B", де A – номер тесту (починаючи з 1), B – шукана величина для даного тесту.

Приклад

Вхідні дані #1
2
6 997
1 2
1 4
3 4
5 3
3 6
7 13
1 2
1 3
1 4
2 5
3 6
4 7
Вихідні дані #1
Case #1: 16
Case #2: 5