Algorithm

A. Cowardly Rooks
time limit per test
2 seconds
memory limit per test
256 megabytes
Problem link- https://codeforces.com/problemset/problem/1749/A
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� (1≤t≤20001≤�≤2000) — the number of testcases.

The first line of each testcase contains two integers n� and m� (1≤n,m≤81≤�,�≤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�� (1≤xi,yi≤n1≤��,��≤�) — 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 & Try With Live Editor

Input

x
–
+
cmd
2
2 2
1 2
2 1
3 1
2 2

Output

x
–
+
cmd
NO
YES
Advertisements

Demonstration

Codeforcess Solution 1749-A A. Cowardly Rooks ,C++, Java, Js and Python,1749-A,Codeforcess Solution

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+