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