ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Later is better than never

About     Problems     Submit solution     Judge status     Standings
Contest is over

A. Rubina's Solitaire

Time limit: 1.0 second
Memory limit: 128 MB
In the evenings Rubina likes to play solitaire. To play the game she uses a family card deck. In the Rubina’s deck there are m · n cards, each of which has one of m suits and a rank from 1 to n. There are no two cards of the same suit and rank simultaneously in the card deck.
To solve this solitaire means to lay out all the cards into m stacks so that all cards in each stack are of the same suit and follow from the bottom up in order of increasing rank. The solitaire begins with Rubina shuffling cards and laying them down in k horizontal rows where the i-th row consists of ai cards. For one move it is allowed to take the rightmost card from any row and move it to the stack with the same suit as the card has. The move is possible only if the top card in this stack is one less with its rank than the card that was moved, or if the stack is empty and the card that was moved has a rank of 1.
Rubina has already shuffled the cards and put them into the rows. Find out if she will be able to solve the solitaire.
Problem illustration

Input

The first line contains the integers m, n and k that are the number of suits, the number of cards in the suit and the number of rows, respectively (1 ≤ n · m ≤ 105; 1 ≤ k ≤ 105). Each of the following k lines contains a description of the next row of cards. The description of i-th row begins with a positive integer ai that is the number of cards in this row. After that in the line with the row description ai pairs of integers bij, cij are listed that are the suit and rank of the card lying in the i-th row at position j from left to right (1 ≤ bijm; 1 ≤ cijn). It is guaranteed that all the cards at the beginning are different and form the Rubina’s deck.

Output

If the solitaire can not be solved, output “NO”. Otherwise, output “YES” in the first line, and in the following n · m lines output the card descriptions in the order they are transferred to the stacks. The description of the card must consists of two integers with a space between them: its suit and rank. If there are several different orders that satisfy the problem requirements, you may output any of them.

Samples

inputoutput
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
Problem Author: Alexander Ipatov, prepared by Oleg Dolgorukov
Problem Source: "Later is better than never" Contest
To submit the solution for this problem go to the Problem set: 2128. Rubina's Solitaire