409549: GYM103630 A Рудольф и сборка компьютеров

A. Рудольф и сборка компьютеровограничение по времени на тест2 секундыограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Рудольф собирает компьютерный класс. У него есть в наличии $$$N$$$ системных блоков и $$$M$$$ комплектующих (мониторов, клавиатур, мышек, колонок). У $$$i$$$-го системного блока есть $$$K_{i}$$$ портов определенных типов. К каждому порту можно подсоединить неограниченное количество устройств, если устройство имеет соответствующий тип подключения. Комплектующие могут быть одного из четырех видов (монитор, клавиатура, мышь, колонки) и имеют один тип подключения, то есть могут подключаться только к системным блокам, имеющим порт этого типа. Устройства, подключенные к одному системному блоку, не могут быть при этом подключены к другому системному блоку.

Рудольф хочет собрать наибольшее количество рабочих компьютеров. Рабочим компьютером считается системный блок, к которому подключено хотя бы одно устройство каждого вида. Помогите Рудольфу узнать, какое максимальное количество компьютеров можно собрать, и выведите номера полностью укомплектованных системных блоков.

Входные данные

Первая строка содержит целое число $$$N$$$ $$$(1 \leq N \leq 12)$$$ — количество системных блоков.

В следующих $$$N$$$ строках входных данных описываются системные блоки, каждый в отдельной строке. Первое число описания $$$K_{i}$$$ $$$(1 \leq K_{i} \leq 50)$$$ — количество портов $$$i$$$-го системного блока. Затем идут $$$K_{i}$$$ целых чисел $$$P_{j}$$$ $$$(1 \leq P_{j} \leq 50)$$$ — тип $$$j$$$-го подключения порта.

Следующая строка содержит целое число $$$M$$$ $$$(1 \leq M \leq 1000)$$$ — количество комплектующих.

В следующих $$$M$$$ строках входных данных описываются комплектующие, каждое в отдельной строке. Описание содержит два целых числа $$$A_{v}$$$, $$$B_{v}$$$ $$$(1 \leq A_{v} \leq 4, 1 \leq B_{v} \leq 50)$$$. Число $$$A_{v}$$$ — вид $$$v$$$-го комплектующего: $$$1$$$ — монитор, $$$2$$$ — клавиатура, $$$3$$$ — мышь, $$$4$$$ — колонки. Число $$$B_{v}$$$ — тип подключения.

Выходные данные

Выведите целое число $$$X$$$ — максимальное количество компьютеров, которые можно укомплектовать. В следующей строке выведите через пробел $$$X$$$ целых чисел — номера системных блоков.

Если наборов системных блоков, позволяющих получить максимальное количество укомплектованных компьютеров, несколько, выведите описание любого из таких наборов.

ПримерВходные данные

3
2 1 2
2 2 3
1 4
9
1 1
1 2
1 4
2 2
2 4
3 4
4 1
3 2
4 4

Выходные данные

2
1 3