Множества в четырёхдольном графе
Множества в четырёхдольном графе
Дан граф, вершины которого разделены на 4 группы, а рёбра соединяют только вершины из групп I и II, II и III, III и IV, IV и I. Вам нужно найти, какое максимальное количество непересекающихся 4-вершинных циклов можно выбрать в этом графе. Каждый цикл должен содержать по одной вершине из каждой группы, и вершины из групп I и II, II и III, III и IV, IV и I должны быть соединены ребром.
Входные данные
Первая строка ввода содержит количество тестов T (1 ≤ T ≤ 10). Первая строка каждого теста содержит 4 числа: N1, N2, N3, N4 – количества вершин в группах I, II, III и IV (1 ≤ N1, N2, N4 ≤ 10, 1 ≤ N3 ≤ 7).
Далее следуют N1 строк. (2i+1)-я строка (0 ≤ i ≤ N1 – 1) содержит количество вершин из группы II, смежных с i-й вершиной из группы I, а затем – номера этих вершин. (2i+2)-я строка содержит количество вершин из группы IV, смежных с i-й вершиной из группы I, а затем – номера этих вершин. (Вершины в каждой группе занумерованы начиная с 0.)
Далее следуют 2N3 строк. (2i+1)-я строка (0 ≤ i ≤ N3 – 1) содержит количество вершин из группы II, смежных с i-й вершиной из группы III, а затем – номера этих вершин. (2i+2)-я строка содержит количество вершин из группы IV, смежных с i-й вершиной из группы III, а затем – номера этих вершин.
Выходные данные
Выведите T строк вида Case #A: B, где A – номер теста (начиная с 1), B – искомая величина для данного теста.
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
Case #1: 1 Case #2: 3