Задача G. Game of Mafia ≡

Условие

Петя и его друзья решили поиграть в популярную игру Мафия. Каждый игрок в этой игре получает одну из ролей: шериф, мафиози или мирный гражданин. После раздачи ролей город засыпает, все игроки закрывают глаза, после чего их открывают только мафиози, чтобы познакомиться друг с другом, другие игроки при этом не будут знать наверняка кто есть кто. Игра поделена на раунды, один раунд состоит из дня и ночи. Днем игроки общаются и голосуют за то, кого отправить в тюрьму. Ночью шериф ищет мафию, а мафия кого-то убивает.

Всего на игру собралось N человек. Для такого количества игроков оптимальное распределение ролей следующее: один шериф и M мафиози.

Обычно в партиях Мафии те, кого убивают или сажают в первые раунды, очень грустят, так как они толком не успели поиграть, и теперь должны ждать завершения партии. Петя и его друзья очень дружные, поэтому они решили договориться, что в первые несколько ночей мафия никого не будет убивать, и голосование за посадку в тюрьму проводиться не будет. Так все точно успеют наиграться до того, как начнется основной замес.

Спустя несколько раундов Петя попросил каждого участника назвать M других игроков, тех кто, по их мнению, является мафией. За это время шериф успел проверить всех игроков, так что он точно знает кто мафия, и назовёт именно их. С другой стороны, мафиози не станут помогать другим игрокам, поэтому не будут выдавать друг друга.

Помогите Пете выяснить, можно ли по полученной информации однозначно определить мафию.

Формат входных данных

В первой строке входных данных записаны целые числа N и M — общее количество игроков и количество мафиози соответственно.

Далее следует N строк, i-я строка содержит M различных целых чисел a_i,j — предположения i-о игрока касательно того, кто является мафией.

Гарантируется, что входные данные корректные и соответствуют ситуации описанной в условии.

Формат выходных данных

В единственной строке выведите YES или NO — можно ли однозначно определить игроков с ролью мафиози.

Ограничения

6 ≤ N ≤ 500

1 ≤ M ≤ ⌊ N2⌋

1 ≤ a_i,j ≤ N

Пояснение к примерам

В первом примере мафией являются игроки 3 и 5.

Во втором примере мафией могут быть пары игроков 1 и 5, 3 и 7, 4 и 8.

Примеры тестов

6 2
3 4
4 1
6 2
3 5
2 4
5 2

YES

8 2
3 7
7 5
1 8
7 1
2 7
2 5
4 8
5 1

NO