ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Лучше поздно, чем никогда

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

A. Пасьянс Рубины

Ограничение времени: 1.0 секунды
Ограничение памяти: 128 МБ
Рубина по вечерам любит раскладывать пасьянс. Для этого она использует фамильную колоду карт. В колоде Рубины m · n карт, каждая из которых имеет одну из m мастей и достоинство от 1 до n. В колоде нет двух карт одной масти с одинаковым достоинством.
Разложить пасьянс — это значит разложить все карты на m стопок так, чтобы в каждой стопке все карты были одной масти и следовали снизу вверх в порядке возрастания достоинства. Пасьянс начинается с того, что Рубина тасует карты и раскладывает их рубашкой вниз в k горизонтальных рядов, i-й ряд состоит из ai карт. За один ход разрешается взять самую правую карту из какого-нибудь ряда и переместить её в стопку, соответствующую масти этой карты. Ход возможен лишь в том случае, если верхняя карта в этой стопке на единицу меньше достоинством, чем перемещаемая карта, либо если стопка пуста, а перемещаемая карта имеет достоинство 1.
Рубина уже перетасовала карты и разложила их в ряды. Выясните, получится ли у неё разложить пасьянс.
Problem illustration

Исходные данные

В первой строке записаны целые числа m, n и k — количество мастей, количество карт в масти и количество рядов соответственно (1 ≤ n · m ≤ 105; 1 ≤ k ≤ 105). Каждая из следующих k строк содержит описание очередного ряда карт. Описание i-го ряда начинается с целого положительного числа ai — количества карт в этом ряду. Далее в строке с описанием ряда перечислено ai пар чисел bij, cij — масть и достоинство карты, лежащей в i-м ряду на позиции j слева направо (1 ≤ bijm; 1 ≤ cijn). Гарантируется, что все карты на входе различны и вместе образуют колоду Рубины.

Результат

Если пасьянс разложить не удастся, выведите «NO». Иначе в первой строке выведите «YES», а в следующих n · m строках выведите описания карт в порядке их перекладывания в стопки. Описание карты должно представлять из себя два целых числа через пробел — её масть и достоинство. Если существует несколько различных порядков, удовлетворяющих условию задачи, можно вывести любой из них.

Примеры

исходные данныерезультат
2 3 2
3 1 3 2 3 1 1
3 1 2 2 2 2 1
YES
1 1
2 1
2 2
2 3
1 2
1 3
2 3 2
3 1 3 2 2 1 2
3 1 1 2 3 2 1
NO
Автор задачи: Александр Ипатов, подготовка — Олег Долгоруков
Источник задачи: Контест "Лучше поздно, чем никогда"
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2128. Пасьянс Рубины