{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eConsider a tree-graph. In each node of this tree one or more tokens can be placed. After the placement a node with two or more tokens can be selected and two tokens can be removed from the selected node and one token can be placed to any adjacent node to the selected one. Such operation can be repeated several times. Your task is to find the maximal number of tokens (modulo \u003cstrong\u003eM\u003c/strong\u003e) that can be placed on the tree nodes to fulfill the following condition: there exists at least one node, to which it is impossible to move a token applying given operations.\u003c/p\u003e\n\n\u003cp\u003e\u003ch2\u003eInput\u003c/h2\u003e\u003c/p\u003e\n\n\u003cp\u003eFirst line of input contains the quantity of tests \u003cstrong\u003eT\u003c/strong\u003e (\u003cstrong\u003e1\u003c/strong\u003e ≤ \u003cstrong\u003eT\u003c/strong\u003e ≤ \u003cstrong\u003e100\u003c/strong\u003e).\u003c/p\u003e\n\n\u003cp\u003eFirst line of each test case contains two numbers: \u003cstrong\u003eN\u003c/strong\u003e (\u003cstrong\u003e2\u003c/strong\u003e ≤ \u003cstrong\u003eN\u003c/strong\u003e ≤ \u003cstrong\u003e30000\u003c/strong\u003e) -- the number of nodes in the tree and \u003cstrong\u003eM\u003c/strong\u003e (\u003cstrong\u003e2\u003c/strong\u003e ≤ \u003cstrong\u003eM^31--1\u003c/strong\u003e ≤ 2). Then \u003cstrong\u003eN\u003c/strong\u003e--\u003cstrong\u003e1\u003c/strong\u003e lines follows, each of which contains \u003cstrong\u003e2\u003c/strong\u003e adjacent node numbers (nodes are numbered from \u003cstrong\u003e1\u003c/strong\u003e to \u003cstrong\u003eN\u003c/strong\u003e) separated by space.\u003c/p\u003e\n\n\u003cp\u003e\u003ch2\u003eOutput\u003c/h2\u003e\u003c/p\u003e\n\n\u003cp\u003eOutput \u003cstrong\u003eT\u003c/strong\u003e lines of the form \"\u003cstrong\u003eCase\u003c/strong\u003e #\u003cstrong\u003eA\u003c/strong\u003e: \u003cstrong\u003eB\u003c/strong\u003e\", where \u003cstrong\u003eA\u003c/strong\u003e is the number of test (beginning from \u003cstrong\u003e1\u003c/strong\u003e), \u003cstrong\u003eB\u003c/strong\u003e is the desired number for this test case.\u003c/p\u003e\n\n"}},{"title":"Example","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n6 997\n1 2\n1 4\n3 4\n5 3\n3 6\n7 13\n1 2\n1 3\n1 4\n2 5\n3 6\n4 7\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 16\nCase #2: 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}