You are given two binary strings SS and PP. You need to convert SS into PP using the following operation any number of times (possibly zero):

You are given two binary strings SS and PP. You need to convert SS into PP using the following operation any number of times (possibly zero):

  • Pick three binary values XXYY, and ZZ, such that at least one of them is equal to 11 and at least one of them is equal to 00. Then, pick three distinct indices iijj, and kk, and assign Si=XSi=XSj=YSj=Y, and Sk=ZSk=Z.

Determine whether it’s possible to convert SS into PP.

Input Format

  • The first line contains an integer TT denoting the number of test cases. The TT test cases then follow.
  • The first line of each test case contains NN denoting the length of SS and PP.
  • The second line of each test case contains SS.
  • The third line of each test case contains PP.

Output Format

For each test case, output on one line YES if it is possible to convert SS to PP, or NO if it is not possible to do so. Output is case insensitive.

Constraints

  • 1T10001≤T≤1000
  • 3N10003≤N≤1000
  • |S|=|P|=N|S|=|P|=N

Sample Input 1 

2
4
1001
0101
3
111
000

Sample Output 1 

YES
NO

Explanation

  • For the first test case, we choose X=0,Y=1X=0,Y=1 and Z=1Z=1. This satisfies the above condition. Three indices (i,j,k)(i,j,k) are chosen as (1,2,4)(1,2,4), and (A1,A2,A4)(A1,A2,A4) are then assigned as (0,1,1)(0,1,1) respectively. After this operation, SS transforms into 0101.

  • For the second test case, no set of any operations is possible to make SS equals to PP.

Fake GCD solution codechef 

Cars and Bikes solution codechef

Adjacency Hatred solution codechef

 Zebra Crossing solution codechef

Leave a Reply

Your email address will not be published. Required fields are marked *

*