Мама попросила Лену убрать свою комнату перед тем, как Лена сядет за свою любимую онлайн игрушку. Лена уже почти справилась: заправила кровать, убрала одежду в шкаф и даже отнесла все фантики от конфет в мусорку. Осталось последнее дело — расставить на полке все разбросанные по комнате коллекционные упаковки с супергероями.
У Лены есть n коробок, пронумерованных от 1 до n. В коробке с номером i стоят ki супергероев, каждый своего размера aij. Лена хочет поскорее сесть за компьютер, но считает, что абсолютно необходимо расставить коробки с супергероями так, чтобы все супергерои стояли в ряд в порядке неубывания размера. Если это невозможно сделать, уборка комнаты не может быть закончена в принципе. Со времени последней приборки коробок прибавилось, поэтому Лена сама пока не знает, может ли уборка быть закончена или нет.
Лена ценит свои коллекционные коробки с супергероями и не хочет ради уборки их вскрывать, иначе потеряется вся их коллекционная ценность. Лена также любит иногда наслаждаться своей коллекцией супергероев, а прозрачная пленка есть только с одной стороны, поэтому ставить коробку с супергероями задом наперёд тоже нельзя.
Помогите Лене определить, может ли она пойти к маме и сказать, что уборка не может быть закончена, или ей всё-таки придётся расставлять коробки.
Исходные данные
В первой строке дано целое число n — количество коробок с супергероями (1 ≤ n ≤ 100).
В каждой из следующих n строк дается целое число ki — количество супергероев в i-й коробке (1 ≤ ki ≤ 100), а затем ki целых чисел aij — размеры супергероев в том порядке, в котором они расположены в коробке (1 ≤ aij ≤ 104). Числа в одной строке разделены пробелами.
Результат
Выведите «YES
» (без кавычек), если можно расставить коробки так, чтобы супергерои шли по неубыванию размера, и «NO
» (без кавычек) в противном случае.
Примеры
исходные данные | результат |
---|
3
2 1 2
3 7 7 7
1 5
| YES
|
2
2 1 3
1 2
| NO
|
Замечания
В первом примере на первое место нужно поставить первую коробку. Далее должна стоять третья коробка. Далее вторая. Тогда супергерои будут идти в порядке неубывания размера:
1, 2, 5, 7, 7, 7.
Во втором примере как коробки не расставляй, супергероев всё равно не получится поставить в порядке неубывания размера.
Автор задачи: Иван Смирнов
Источник задачи: Уральская командная олимпиада по программированию 2019