Sets in a four-partite graph#105
There is a graph whose vertices are divided into groups. Edges exist only between the following pairs of groups: I and II, II and III, III and IV, IV and I. Your task is to determine the maximum number of disjoint -vertex cycles that can be chosen in this graph. Each cycle must include exactly one vertex from each group, and in the cycle, the vertices from groups I and II, II and III, III and IV, and IV and I must be directly connected by edges.
The first line contains the number of test cases (1 \leq T \leq 10). Each test case starts with a line containing integers: N_1, N_2, N_3, N_4, which represent the number of vertices in groups I, II, III, and IV, respectively (1 \leq N_1, N_2, N_4 \leq 10, 1 \leq N_3 \leq 7).
Then, 2N_1 lines follow describing the adjacency for each vertex in group I. For each (0 \leq i < N_1): - The (2i+1)-st line contains the number of adjacent vertices in group II, followed by their indices. - The (2i+2)-nd line contains the number of adjacent vertices in group IV, followed by their indices. (Vertices in each group are numbered from .)
Next, 2N_3 lines follow describing the adjacency for each vertex in group III. For each (0 \leq i < N_3): - The (2i+1)-st line contains the number of adjacent vertices in group II, followed by their indices. - The (2i+2)-nd line contains the number of adjacent vertices in group IV, followed by their indices.
Print lines, each of the form "Case #: ", where is the test case number (starting from ), and is the required maximum number for that test case.
Example 1