Hide

Problem D
Football!

It is once again the coming of age festival for our $n$ boys in our great Kingdom. As tradition dictates, there will be a series of football games held over a span of $m$ days. Each day, there will be a football game pitting $2$ teams of $n/2$ boys against each other.

The organizing committee is currently accepting proposals to arrange the matchups and which boy should be in which team. However, the committee would like each boy to have a chance to play against all other boys in at least one of those games in the spirit of fairness.

However, there are too many proposals! That is where you, our humble protagonist, comes in. You told the committee, that while you may not be smart enough to come up with a decent scheduling proposal, you are able to write a program to tell which proposal satisfies their condition!

The committee is skeptical of your ability and thus demands you to write the program!

Input

The first line consists of $2$ integers: $n$, $m$, ($1 \leq n \leq 40\, 000$), ($1 \leq m \leq 60$), where $n$ is the number of boys and $m$ is the number of days. $n$ is also guaranteed to be even.

This is followed by $m$ lines, each consisting of a permutation of $n$ integers: $x_1 \ldots x_ n$ ($1 \leq x_ i \leq n$ for all $1 \leq i \leq n$).

This means that the first team consisting of boys $x_1 \ldots x_{\frac{n}{2}}$ will play against the second team consisting of boys $x_{\frac{n}{2} + 1} \ldots x_ n$

Output

You will output YES if the proposal satisfies the committee’s requirement, and NO otherwise.

Sample Input 1 Sample Output 1
6 6
1 6 3 4 5 2
6 4 2 3 1 5
4 2 1 5 6 3
4 5 1 6 2 3
3 2 5 1 6 4
2 3 6 4 1 5
YES
Sample Input 2 Sample Output 2
6 6
3 1 4 5 6 2
5 3 2 4 1 6
5 3 6 4 2 1
6 5 3 2 1 4
5 4 1 2 6 3
4 1 6 2 5 3
NO
CPU Time limit 1 second
Memory limit 1024 MB
Statistics Show
Author
Vuong Hoang Long
Source NUS Competitive Programming
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in