Дистанционный практикум по программированию

В городе имеется N детских садов. Для каждого сада известно количество свободных мест для набора новых детей в младшие группы.

Для приёма заявок от родителей была создана комиссия. Всего в комиссию поступило M заявок. В каждой заявке родители указали список детских садов, которые для них по какой-то причине предпочтительны (например, расположены рядом с домом либо местом работы родителей).

Обработка заявок проводится в порядке, в котором они поступили. Первая заявка гарантированно выполняется. Вторая заявка выполняется в том случае, если при этом возможно также выполнить и первую (возможно, выбрав для неё другой садик). Каждая следующая заявка обрабатывается аналогично — то есть i-я заявка выполняется в том случае, если при этом по-прежнему можно выполнить все заявки, признанные выполнимыми на предыдущих шагах.

Определите, какие заявки получится выполнить, и укажите подходящий вариант распределения заявок по детским садам.

Примечание. Вероятно, невыполненные заявки комиссия потом всё же распределит по оставшимся местам, но уже без учёта предпочтений. Впрочем, к решению данной задачи это совершенно не относится.

 

Входные данные. Первая строка входных данных содержит два разделенных пробелом целых числа N и M, где N — количество детских садов в городе, M — количество поданных заявок (1 ≤ N ≤ 100; 1 ≤ M ≤ 1000).

Вторая строка содержит N разделённых пробелом целых чисел — количество мест в каждом садике.

Каждая из следующих M строк содержит описание очередной заявки. Описание заявки представляет собой несколько разделенных пробелом целых чисел — вначале идёт количество садиков Q_i, а затем Q_i чисел — номера садиков (в диапазоне от 1 до N).

 

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

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

 

Примеры

Входные данные	Выходные данные
2 5 2 1 1 2 2 1 2 1 2 1 1 1 2	3 1 2 2 1 4 1