## Algorithm

A. Cowardly Rooks
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There's a chessboard of size n×n�×�m rooks are placed on it in such a way that:

• no two rooks occupy the same cell;
• no two rooks attack each other.

A rook attacks all cells that are in its row or column.

Is it possible to move exactly one rook (you can choose which one to move) into a different cell so that no two rooks still attack each other? A rook can move into any cell in its row or column if no other rook stands on its path.

Input

The first line contains a single integer t (1t20001≤�≤2000) — the number of testcases.

The first line of each testcase contains two integers n and m (1n,m81≤�,�≤8) — the size of the chessboard and the number of the rooks.

The i-th of the next m lines contains two integers xi�� and yi�� (1xi,yin1≤��,��≤�) — the position of the i-th rook: xi�� is the row and yi�� is the column.

No two rooks occupy the same cell. No two rooks attack each other.

Output

For each testcase, print "YES" if it's possible to move exactly one rook into a different cell so that no two rooks still attack each other. Otherwise, print "NO".

Example
input
Copy
2
2 2
1 2
2 1
3 1
2 2
output
Copy
NO
YES

Note

In the first testcase, the rooks are in the opposite corners of a 2×22×2 board. Each of them has a move into a neighbouring corner, but moving there means getting attacked by another rook.

In the second testcase, there's a single rook in a middle of a 3×33×3 board. It has 44 valid moves, and every move is fine because there's no other rook to attack it.

## Code Examples

### #1 Code Example with C++ Programming

Code - C++ Programming

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define endl '\n'
#define debug(n) cout<<(n)<<endl;
const ll INF = 2e18 + 99;

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);

int t;
cin>>t;
while(t--){
int n;
cin>>n;
int m;
cin>>m;
int rooks[m][2];
for(int i = 0; i < m; i++){
cin>>rooks[i][0]>>rooks[i][1];
}
if(m < n){
cout<<"YES"<<endl;
}
else{
cout<<"NO"<<endl;
}

}

}
Copy The Code &

Input

cmd
2
2 2
1 2
2 1
3 1
2 2

Output

cmd
NO
YES