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