Детские сады
В городе имеется N детских садов. Для каждого сада известно количество свободных мест для набора новых детей в младшие группы. Для приёма заявок от родителей была создана комиссия. Всего в комиссию поступило M заявок. В каждой заявке родители указали список детских садов, которые для них по какой-то причине предпочтительны (например, расположены рядом с домом либо местом работы родителей). Обработка заявок проводится в порядке, в котором они поступили. Первая заявка гарантированно выполняется. Вторая заявка выполняется в том случае, если при этом возможно также выполнить и первую (возможно, выбрав для неё другой садик). Каждая следующая заявка обрабатывается аналогично — то есть i-я заявка выполняется в том случае, если при этом по-прежнему можно выполнить все заявки, признанные выполнимыми на предыдущих шагах. Определите, какие заявки получится выполнить, и укажите подходящий вариант распределения заявок по детским садам. Примечание. Вероятно, невыполненные заявки комиссия потом всё же распределит по оставшимся местам, но уже без учёта предпочтений. Впрочем, к решению данной задачи это совершенно не относится.
Входные данные. Первая строка входных данных содержит два разделенных пробелом целых числа N и M, где N — количество детских садов в городе, M — количество поданных заявок (1 ≤ N ≤ 100; 1 ≤ M ≤ 1000). Вторая строка содержит N разделённых пробелом целых чисел — количество мест в каждом садике. Каждая из следующих M строк содержит описание очередной заявки. Описание заявки представляет собой несколько разделенных пробелом целых чисел — вначале идёт количество садиков Qi, а затем Qi чисел — номера садиков (в диапазоне от 1 до N).
Выходные данные. В первую строку выходных данных выведите целое число K —количество заявок, которые получилось удовлетворить. В каждой из следующих K строк выведите два разделенных пробелом целых числа — номер очередной заявки и номер назначенного ей детского сада. Номера заявок в выводе должны идти по возрастанию. Если возможны несколько вариантов назначения найденных заявок по детским садам, то выведите любой.
Примеры
| |||||||||||
|