Фишки
Рассмотрим граф-дерево. В каждый узел этого дерева можно поместить одну или несколько фишек. После расположения фишек можно выбрать узел дерева, в котором есть две или больше фишек, и убрать из него две фишки, при этом поместив одну фишку в любой из соседних узлов. Такую операцию можно повторять несколько раз. Ваша задача найти максимальное количество фишек (по модулю 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 – искомая величина для данного теста.