B2. Character Swap (Hard Version)

  • Quiz
  • AC
  • 解説
    • 文字種ごとに文字数が偶数じゃない場合は等分できないのでNo。それ以外を考える
    • sの先頭から合わせていけばいい
    • s[i]に合わせたいものが
      • i+1以降のsにある場合、1回のswapでi番目は揃えられる ・・・（１）
      • i+1以降のsにある場合、(それをj番目として) s[j], t[j]をswapし、その後（１）をすればいい
    • よってswap回数は2Nに収まる
// for codeforces
void solve(){
  ll N;
  cin>>N;
  string s,t;cin>>s>>t;
  
  // check
  map<char,ll> mp;
  for(char c : s+t){
    mp[c]++;
  }
  for(auto pa : mp){
    ll cnt = pa.second;
    if(cnt%2==1){
      p_no(); return;
    }
  }
  for(auto& pa : mp){
    pa.second /= 2;
  }

  vector<PII> Ans;
  // 分配可能
  rep(i,N){
    if(s[i]==t[i]) continue;
    char c = s[i];
    // s[i]に合わせる
    bool swapped = false;
    FOR(j,i+1,N){
      if(s[j]==c){
        swap(t[i],s[j]);
        Ans.push_back({j,i});
        swapped = true;
        break;
      }
    }
    if(swapped) continue;
    // t側に目的の文字があるので探してs側に送る
    FOR(j,i+1,N){
      if(t[j]==c){
        swap(t[j],s[j]);
        Ans.push_back({j,j});
        break;
      }
    }
    // 上と同様
    FOR(j,i+1,N){
      if(s[j]==c){
        swap(t[i],s[j]);
        Ans.push_back({j,i});
        break;
      }
    }
  }
  p_yes();
  p(SZ(Ans));
  for(auto pa : Ans){
    p2(pa.first+1, pa.second+1);
  }
}

int main(){
    // input
    ll N; 
    cin>>N;
    while(N--)solve();
    return 0;
}