Can You Reach The End solution codechef

Can You Reach The End solution codechef

You are given a positive integer NN. Consider a square grid of size N×NN×N, with rows numbered 11 to NN from top to bottom and columns numbered 11 to NN from left to right. Initially you are at (1,1)(1,1) and you have to reach (N,N)(N,N). From a cell you can either move one cell to the right or one cell down (if possible). Formally, if you are at (i,j)(i,j), then you can either move to (i+1,j)(i+1,j) if i<Ni<N, or to (i,j+1)(i,j+1) if j<Nj<N.

Can You Reach The End solution codechef

There are exactly NN blocks in the grid, such that each row contains exactly one block and each column contains exactly one block. You can’t move to a cell which contains a block. It is guaranteed that blocks will not placed in (1,1)(1,1) and (N,N)(N,N).

You have to find out whether you can reach (N,N)(N,N).

Input Format

Can You Reach The End solution codechef

  • The first line contains TT – the number of test cases. Then the test cases follow.
  • The first line of each test case contains NN – the size of the square grid.
  • The ii-th line of the next NN lines contains two integers XiXi and YiYi indicating that (Xi,Yi)(Xi,Yi) is the position of a block in the grid.

Output Format

Can You Reach The End solution codechef

For each test case, if there exists a path from (1,1)(1,1) to (N,N)(N,N), output YES, otherwise output NO.

You may print each character of the string in uppercase or lowercase (for example, the strings yEsyesYes and YES will all be treated as identical).

Constraints

  • 1T10001≤T≤1000
  • 2N1062≤N≤106
  • 1Xi,YiN1≤Xi,Yi≤N
  • (Xi,Yi)(1,1)(Xi,Yi)≠(1,1) and (Xi,Yi)(N,N)(Xi,Yi)≠(N,N) for all 1iN1≤i≤N
  • XiXjXi≠Xj and YiYjYi≠Yj for all 1i<jN1≤i<j≤N
  • Sum of NN over all test cases does not exceed 106106

Sample Input 1

Can You Reach The End solution codechef

2
3
1 2
2 3
3 1
2
1 2
2 1

Sample Output 1

Can You Reach The End solution codechef

YES
NO

Explanation

Can You Reach The End solution codechef

  • Test case 11: We can follow the path (1,1)(2,1)(2,2)(3,2)(3,3)(1,1)→(2,1)→(2,2)→(3,2)→(3,3).

  • Test case 22: We can’t move from the starting point, so it is impossible to reach (N,N)(N,N).
  • For Solution

    Click Here!

Leave a Comment

Your email address will not be published.