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.
Specifications
Input
First line of input contains the quantity of tests T (1 ≤ T ≤ 10). First line of each test contains 4 numbers: N1, N2, N3, N4 – the quantities of vertices in groups I, II, III and IV (1 ≤ N1, N2, N4 ≤ 10, 1 ≤ N3 ≤ 7).
Then 2N1 lines follow. (2i+1)-st line (0 ≤ i ≤ N1–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 2N3 lines follow. (2i+1)-st line (0 ≤ i ≤ 2N3–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.
Problem information
Time Limit: 15 secondsMemory Limit: 64 MB
Balls for the passed test: 50
Complexity: 50% 1/2
Example
Example input2 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 |
Example outputCase #1: 1 Case #2: 3 |
| ← Rope pulling – 2 | Problems | Tokens → |