Chips#106
Consider a tree.
In each node of the tree, you may place one or more chips. After placing the chips, you may repeatedly perform the following operation: select any node containing at least two chips, remove two chips from this node, and add one chip to any adjacent node.
Your task is to determine the maximum number of chips (not exceeding ) that can be placed on the nodes so that the following condition is satisfied: there exists at least one node to which it is impossible to add a chip by repeatedly applying the allowed operation.
The first line contains an integer (1 \leq T \leq 100) — the number of test cases.
Each test case begins with a line containing two integers: (2 \leq N \leq 30000), the number of nodes in the tree, and (2 \leq M \leq 2^{31} - 1).
The next N-1 lines each contain two integers: the indices of adjacent nodes (nodes are numbered from to ), separated by a space.
Print lines. For each test case, output a line in the format "Case #A: B", where is the test case number (starting from ), and is the answer for this test case.
Example 1