Problem G. Game of Mafia ≡

Statement

Petya and his friends decided to play the popular game Mafia. Each player in this game receives one of the roles: sheriff, mafioso, or civilian. After roles are assigned, the city falls asleep, all players close their eyes, and only the mafiosi open theirs to get to know each other. Other players won't know for sure who is who. The game is divided into rounds, with one round consisting of a day and a night. During the day, players communicate and vote on whom to send to prison. At night, the sheriff searches for the mafia, and the mafia kills someone.

A total of N people gathered for the game. For such a number of players, the optimal distribution of roles is as follows: one sheriff and M mafiosi.

Usually, in Mafia games, those who are killed or sent to prison in the early rounds feel very sad since they haven't had a proper chance to play and must now wait for the game to finish. Petya and his friends are very friendly, so they agreed that in the first few nights, the mafia won't kill anyone, and there won't be a vote for imprisonment. This way, everyone will have a chance to play before the main chaos begins.

After a few rounds, Petya asked each participant to name M other players whom they believe are part of the mafia. During this time, the sheriff managed to check all players, so he knows exactly who the mafia is and will name them. On the other hand, the mafiosi won't help other players, so they won't expose each other.

Help Petya determine if it's possible to unequivocally identify the mafia based on the information received.

Input format

The first line of input contains two integers N and M — the total number of players and the number of mafiosi, respectively.

Next are N lines, where the i-th line contains M distinct integers a_i,j — the i-th player's assumptions about who the mafia is.

It is guaranteed that the input data is correct and corresponds to the situation described in the condition.

Output format

In a single line, output YES or NO — whether it is possible to unambiguously determine the players with the role of mafiosi.

Constraints

6 ≤ N ≤ 500

1 ≤ M ≤ ⌊ N2⌋

1 ≤ a_i,j ≤ N

Notes on samples

In the first example, players 3 and 5 are the mafia.

In the second example, the mafia could be pairs of players 1 and 5, 3 and 7, 4 and 8.

Sample tests

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

Explanation

Определить, может ли конкретный участник быть шерифом, можно за O(M²). Для этого нужно проверить, что его показания указывают на участников, каждый из которых не называл других из этого списка. Это можно сделать с помощью вспомогательного двумерного булевого массива U такого, что U_ij = true тогда, когда i-й участник назвал j-о участника. Таким образом, за O(N * M²) можно найти всех потенциальных шерифов.

Если потенциальный шериф оказался единственным — ответ YES, в противном случае необходимо сверить показания шерифов между собой. Например, может быть случай, когда потенциальных шерифов оказалось несколько, но все назвали один и тот же набор участников. В этом случае ответ также YES. Во всех остальных случаях ответ NO.