#include <bits/stdc++.h>

using namespace std;

int main() {
  auto ok = [](string s) {
    for (int i = 1; i < (int)s.size(); ++i)
      if (s[i - 1] == s[i]) return false;
    return true;    
  };
  
  int t;
  cin >> t;
  while (t--) {
    int n, m;
    string s, t;
    cin >> n >> m >> s >> t;
    bool f = false;
    for (int x = 0; x < 2; ++x) {
      string cs = s, ct = t;
      for (int i = 0; i < n; ++i) {
        f |= ok(cs) && ok(ct);
        ct.push_back(cs.back());
        cs.pop_back();
      }
      swap(n, m);
      swap(s, t);   
    }
    cout << (f ? "YES\n" : "NO\n");
  }
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, m;
    string s, t;
    cin >> n >> m >> s >> t;
    reverse(t.begin(), t.end());
    s += t;
    int cnt = 0;
    for (int i = 1; i < n + m; ++i) cnt += s[i - 1] == s[i];
    cout << (cnt <= 1 ? "YES\n" : "NO\n");
  }
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k;
    int L = 0, R = 55;
    while (n--) {
      int l, r;
      cin >> l >> r;
      if (l <= k && k <= r)
        L = max(L, l), R = min(R, r);
    }
    cout << (L == R ? "YES\n" : "NO\n");
  }
}

#include <bits/stdc++.h>

using namespace std;

using li = long long;

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<li> a(n), b(n);
    for (auto& x : a) cin >> x;
    for (auto& x : b) cin >> x;
    vector<li> sum(n + 1);
    for (int i = 0; i < n; ++i) sum[i + 1] = sum[i] + b[i];
    vector<li> cnt(n + 1), add(n + 1);
    for (int i = 0; i < n; ++i) {
      int j = upper_bound(sum.begin(), sum.end(), a[i] + sum[i]) - sum.begin() - 1;
      cnt[i] += 1;
      cnt[j] -= 1;
      add[j] += a[i] - sum[j] + sum[i];
    }
    for (int i = 0; i < n; ++i) {
      cout << cnt[i] * b[i] + add[i] << ' ';
      cnt[i + 1] += cnt[i];   
    }
    cout << '\n';
  }
}

#include <bits/stdc++.h>
 
using namespace std;

const int MOD = 998244353;

int add(int x, int y)
{
    return ((x + y) % MOD + MOD) % MOD;
}

int mul(int x, int y)
{
    return x * 1ll * y % MOD;   
}

int binpow(int x, int y)
{
    int z = 1;
    while(y)
    {
        if(y % 2 == 1) z = mul(z, x);
        x = mul(x, x);
        y /= 2;
    }
    return z;
}

int inv(int x)
{
    return binpow(x, MOD - 2);    
}

int divide(int x, int y)
{
    return mul(x, inv(y));
}

int main()
{
    int n;
    cin >> n;
    int ans = 1;
    for(int i = 1; i <= n / 6; i++)
        ans = mul(ans, divide(i + n / 6, i));
    for(int i = 0; i < n / 3; i++)
    {
        vector<int> a(3);
        for(int j = 0; j < 3; j++)
            cin >> a[j];
        int mn = *min_element(a.begin(), a.end());
        int cnt_min = count(a.begin(), a.end(), mn);
        ans = mul(ans, cnt_min);
    }
    cout << ans << endl;
}

import java.util.*

fun main() {
    repeat(readln().toInt()) {
        val n = readln().toInt()
        var h = readln().split(' ').map { it.toInt() }

        val d = Array(2) { LongArray(n) { 0 } }
        for (tp in 0..1) {
            val s = Stack<Pair<Int, Int>>()

            for (i in h.indices) {
                while (s.isNotEmpty() && s.peek().first > h[i] - i)
                    s.pop()
                var j = maxOf(-1, i - h[i])
                if (s.isNotEmpty())
                    j = maxOf(j, s.peek().second)

                val len = (i - j).toLong()
                d[tp][i] = len * h[i] - len * (len - 1) / 2
                if (j >= 0 && len < h[i])
                    d[tp][i] += d[tp][j]

                s.push(Pair(h[i] - i, i))
            }
            h = h.reversed()
        }
        d[1] = d[1].reversedArray()

        var ans = 1e18.toLong()
        val sum = h.fold(0L) { total, it -> total + it }
        for (i in h.indices) {
            val cur = sum - d[0][i] - d[1][i] + 2 * h[i]
            ans = minOf(ans, cur)
        }
        println(ans)
    }
}

#include <bits/stdc++.h>
 
using namespace std;
 
#define forn(i, n) for(int i = 0; i < int(n); i++) 

vector<vector<int>> g;
vector<int> req;
vector<char> used;

vector<int> d;

bool dfs(int v, int p = -1){
    d[v] = 0;
    for (int u : g[v]) if (u != p){
        if (!dfs(u, v)) return false;
        if (!used[u]) d[v] = max(d[v], d[u] + 1);
    }
    if (req[v] == 0 || d[v] >= req[v]) return true;
    if (p == -1 || used[p]) return false;
    used[p] = true;
    req[p] = req[v] - 1;
    return true;
}

int main(){
    int t;
    scanf("%d", &t);
    while (t--){
        int n;
        scanf("%d", &n);
        g.assign(n, {});
        d.resize(n);
        forn(i, n - 1){
            int v, u;
            scanf("%d%d", &v, &u);
            --v, --u;
            g[v].push_back(u);
            g[u].push_back(v);
        }
        int k;
        scanf("%d", &k);
        vector<int> a(k);
        forn(i, k){
            scanf("%d", &a[i]);
            --a[i];
        }
        int l = 1, r = n;
        int res = 0;
        while (l <= r){
            int m = (l + r) / 2;
            used.assign(n, 0);
            req.assign(n, 0);
            forn(i, k){
                used[a[i]] = true;
                req[a[i]] = m / k + (i < m % k);
            }
            if (dfs(0)){
                res = m;
                l = m + 1;
            }
            else{
                r = m - 1;
            }
        }
        printf("%d\n", res);
    }
}

#include <bits/stdc++.h>
 
using namespace std;
 
#define forn(i, n) for(int i = 0; i < int(n); i++) 

typedef unsigned long long uli;

int main(){
    int t;
    scanf("%d", &t);
    while (t--){
        int n, m;
        scanf("%d%d", &n, &m);
        vector<int> a(n);
        forn(i, n) scanf("%d", &a[i]);
        vector<vector<int>> g(n);
        forn(i, m){
            int v, u;
            scanf("%d%d", &v, &u);
            --v, --u;
            g[v].push_back(u);
            g[u].push_back(v);
        }
        vector<char> rem(n);
        vector<int> d(n);
        forn(i, n) d[i] = g[i].size();
        queue<int> q;
        forn(i, n) if (a[i] == d[i]) q.push(i);
        vector<pair<int, int>> ord;
        while (!q.empty()){
            int v = q.front();
            q.pop();
            rem[v] = true;
            for (int u : g[v]) if (!rem[u]){
                --d[u];
                ord.push_back({v, u});
                if (d[u] == a[u])
                    q.push(u);
            }
        }
        reverse(ord.begin(), ord.end());
        vector<uli> mask(n);
        long long ans = n * 1ll * (n + 1) / 2;
        for (int l = 0; l < n; l += 64){
            int r = min(n, l + 64);
            for (int i = l; i < r; ++i)
                mask[i] = 1ull << (i - l);
            for (const pair<int, int> &it : ord)
                mask[it.first] |= mask[it.second];
            forn(i, n){
                ans -= __builtin_popcountll(mask[i]);
                mask[i] = 0;
            }
        }
        printf("%lld\n", ans);
    }
}