Problem G. Game of Mafia

Author:A. Usmanov   Time limit:1 sec
Input file:Standard input   Memory limit:256 Mb
Output file:Standard output  

Statement

"The city sleeps, the mafia awakens"

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 ai,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 ≤ ai,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

No. Standard input Standard output
1
6 2
3 4
4 1
6 2
3 5
2 4
5 2
YES
2
8 2
3 7
7 5
1 8
7 1
2 7
2 5
4 8
5 1
NO

0.077s 0.014s 13