Sets in a four-partite graph
There is a graph, whose vertices are divided into 4 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 4-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.
Input
First line of input contains the quantity of tests T (1 ≤ T ≤ 10). First line of each test contains 4 numbers: N_1, N_2, N_3, N_4 – the quantities of vertices in groups I, II, III and IV (1 ≤ N_1, N_2, N_4 ≤ 10, 1 ≤ N_3 ≤ 7).
Then 2N_1 lines follow. (2i+1)-st line (0 ≤ i ≤ N_1–1) contains the quantity of vertices from group II, connected with i-th vertex from group I, and then – the numbers of these vertices. (2i+2)-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 0.)
Then 2N_3 lines follow. (2i+1)-st line (0 ≤ i ≤ 2N_3–1) contains the quantity of vertices from group II, connected with i-th vertex from group III, and then – the numbers of these vertices. (2i+2)-nd line contains the number of vertices from group IV, connected with i-th vertex from group III, and then – the numbers of these vertices.
Output
Output T lines of the form "Case #A: B", where A is the number of test (beginning from 1), B is the desired number for this test case.