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

Ural Regional School Programming Contest 2019

About     Problems     Submit solution     Judge status     Standings
Contest is over

G. Cleaning the Room

Time limit: 0.5 second
Memory limit: 256 MB
Mom asked Lena to clean her room before she plays her favorite online game. Lena almost succeeded: she made the bed, put her clothes into the wardrobe and even threw out all the litter. The last chore remaining is to put all the boxes with action figures onto the shelves.
Lena has n boxes, numbered from 1 to n. Box number i contains ki action figures, each of its own size aij. Lena wants to finish quickly, but it’s very important to put all the figures in a non-decreasing order by their size. If it’s impossible, then the cleaning cannot be finished at all. Lena has quite a lot of boxes, so she isn’t sure if it can be done.
Lena values her boxes with action figures a lot, and she would never open one, because that would require to tear the wrapping. She also enjoys admiring all the figures, and the boxes only have one clear side, so putting a box back to front is out of question.
Help Lena to see if she could tell mom that cleaning cannon be finished, or if it’s possible and she has to arrange the boxes on the shelf anyway.

Input

The first line contains one integer n — the amount of boxes with action figures (1 ≤ n ≤ 100).
Each of next n lines contains a integer ki — amount of figures in i-th box (1 ≤ ki ≤ 100), followed by ki integers aij — sizes of action figures in order from left to right (1 ≤ aij ≤ 104). Integers in one line are separated with spaces.

Output

Print “YES” (without quotes), if boxes can be arranged in such a way that action figues would be in a non-decreasing order by their size. Otherwise, print “NO” (without quotes).

Samples

inputoutput
3
2 1 2
3 7 7 7
1 5
YES
2
2 1 3
1 2
NO

Notes

In the first example, the first box goes first, then the third box, then the second box. That puts figures in a non-decreasing order by their size: 1, 2, 5, 7, 7, 7.
In the second example, there is no arrangement that puts figures in a non-decreasing order.
Problem Author: Ivan Smirnov
To submit the solution for this problem go to the Problem set: 2144. Cleaning the Room