Solution - 1749A - Cowardly Rooks - C++ solution codeforces

Cowardly Rooks solution codeforces


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×nm 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 (1t2000) — the number of testcases.

The first line of each testcase contains two integers n and m (1n,m8) — 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,yin) — 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×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×3 board. It has 4 valid moves, and every move is fine because there's no other rook to attack it.


Solution in C++ / C / Python:
#include<bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;

int main(){
   

    long long c;
    cin>>c;

    long long n, m;
   
    //for(long long i=0; i<c; i++){
    while(c--){
        cin>>n>>m;
        long long x,y;
        for (long long j = 0; j < m; j++)
        {
            cin >> x >> y;
        }
       
        if(m==n){
            cout << "No" << endl;
        }else{
            cout << "Yes" << endl;
        }
    }

    return 0;
}

Comments

Popular posts from this blog

Whiteboarding Interviews

Version Control with Git: A Beginner’s Guide

Callback function in JavaScript