{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eThere is a graph, whose vertices are divided into \u003cstrong\u003e4\u003c/strong\u003e groups, and the edges connect only the vertices from groups I and II, II and III, III and IV, IV and I. You have find, what maximal quantity of non-intersecting \u003cstrong\u003e4\u003c/strong\u003e-vertice cycles could be choosed in this graph. Each cycle must contain exactly one vertex from each group, and the vertices from groups I and II, II and III, III and IV, IV and I must be connected by an edge.\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\u003e10\u003c/strong\u003e). First line of each test contains 4 numbers: \u003cstrong\u003eN_1\u003c/strong\u003e, \u003cstrong\u003eN_2\u003c/strong\u003e, \u003cstrong\u003eN_3\u003c/strong\u003e, \u003cstrong\u003eN_4\u003c/strong\u003e -- the quantities of vertices in groups I, II, III and IV (\u003cstrong\u003e1\u003c/strong\u003e ≤ \u003cstrong\u003eN_1\u003c/strong\u003e, \u003cstrong\u003eN_2\u003c/strong\u003e, \u003cstrong\u003eN_4\u003c/strong\u003e ≤ \u003cstrong\u003e10\u003c/strong\u003e, \u003cstrong\u003e1\u003c/strong\u003e ≤ \u003cstrong\u003eN_3\u003c/strong\u003e ≤ \u003cstrong\u003e7\u003c/strong\u003e).\u003c/p\u003e\n\n\u003cp\u003eThen \u003cstrong\u003e2N_1\u003c/strong\u003e lines follow. \u003cstrong\u003e(2i+1)\u003c/strong\u003e-st line (\u003cstrong\u003e0\u003c/strong\u003e ≤ \u003cstrong\u003ei\u003c/strong\u003e ≤ \u003cstrong\u003eN_1\u003c/strong\u003e--1) contains the quantity of vertices from group II, connected with \u003cstrong\u003ei\u003c/strong\u003e-th vertex from group I, and then -- the numbers of these vertices. \u003cstrong\u003e(2i+2)\u003c/strong\u003e-nd line contains the number of vertices from group IV, connected with i-th vertex from group I, and then -- the numbers of these vertices. (Vertices in each group are numbered beginning from \u003cstrong\u003e0\u003c/strong\u003e.)\u003c/p\u003e\n\n\u003cp\u003eThen \u003cstrong\u003e2N_3\u003c/strong\u003e lines follow. \u003cstrong\u003e(2i+1)\u003c/strong\u003e-st line (\u003cstrong\u003e0\u003c/strong\u003e ≤ \u003cstrong\u003ei\u003c/strong\u003e ≤ \u003cstrong\u003e2N_3\u003c/strong\u003e--1) contains the quantity of vertices from group II, connected with \u003cstrong\u003ei\u003c/strong\u003e-th vertex from group III, and then -- the numbers of these vertices. \u003cstrong\u003e(2i+2)\u003c/strong\u003e-nd line contains the number of vertices from group IV, connected with \u003cstrong\u003ei\u003c/strong\u003e-th vertex from group III, and then -- the numbers of these vertices.\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 1), \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\n1 3 2 4\n3 0 1 2\n4 0 1 2 3\n2 0 1\n1 0\n2 1 2\n2 1 3\n4 7 4 7\n3 0 1 5\n3 0 1 5\n3 0 2 6\n3 0 2 6\n3 1 2 6\n3 1 2 6\n3 0 1 2\n3 0 1 2\n2 0 2\n2 0 2\n1 0\n1 0\n2 1 0\n2 1 0\n2 0 1\n2 0 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 1\nCase #2: 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}