Question
Binary Conversion
You are given binary strings S and T, each of length N, and an integer K.
Find whether it is possible to convert string S to T by making exactly K operations of the following type:
- Choose distinct indices i and j (1 ≤ i, j ≤ N)
- Swap Si with Sj.
Input
The first line of input will contain a single integer T, denoting the number of test cases.
Each test case consists of multiple lines of input.
The first line of each test case contains two space-separated integers N and K - the length of the string and the number of operations, respectively.
The second line contains the binary string S of length N.
The third line contains the binary string T of length N.
Constraints
1 ≤ T ≤ 1200
2 ≤ N ≤ 105
1 ≤ K ≤ N
Si, Ti ∈ {0, 1}
The sum of N over all test case won't exceed 2x105.
Each test case consists of multiple lines of input.
The first line of each test case contains two space-separated integers N and K - the length of the string and the number of operations, respectively.
The second line contains the binary string S of length N.
The third line contains the binary string T of length N.
Constraints
1 ≤ T ≤ 1200
2 ≤ N ≤ 105
1 ≤ K ≤ N
Si, Ti ∈ {0, 1}
The sum of N over all test case won't exceed 2x105.
Output
For each test case, output on a new line, Yes, if it is possible to convert string S to T by making exactly K operations. Otherwise, output No.
Example
Sample Input
2
2 2
01
10
4 2
1101
0111
Sample Output
No
Yes
Explanation
Test case 1: The only operation we can perform on S, is swapping S1, S2. Thus, performing 2 operations would convert S as 01 -> 10 -> 01, which is not equal to T.
Test case 2: We can convert string S = 1101 to T = 0111 using K = 2 operations:
1. Select indices i = 3 and j = 4 and swap S3 and S4 to obtain 1110.
2. Select indices i = 1 and j = 4 and swap S1 and S4 to obtain 0111, which is same as T.
2
2 2
01
10
4 2
1101
0111
Sample Output
No
Yes
Explanation
Test case 1: The only operation we can perform on S, is swapping S1, S2. Thus, performing 2 operations would convert S as 01 -> 10 -> 01, which is not equal to T.
Test case 2: We can convert string S = 1101 to T = 0111 using K = 2 operations:
1. Select indices i = 3 and j = 4 and swap S3 and S4 to obtain 1110.
2. Select indices i = 1 and j = 4 and swap S1 and S4 to obtain 0111, which is same as T.