#line 1 "a.cpp" // https://qandori.github.io/cp-library/ #include #include using namespace std; using std::cin, std::cout, std::cerr; #define vec vector typedef long double ld; #if LONG_MAX == 2147483647L #undef long #define long long long #endif #define uint unsigned int #define ulong unsigned long #define overload3(a, b, c, name, ...) name #define rep3(i, a, b) for (int i = (a); i < (b); i++) #define rep2(i, n) rep3(i, 0, n) #define rep1(n) rep2(__i__, n) #define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__) #define per3(i, a, b) for (int i = (b) - 1; i >= (a); i--) #define per2(i, n) per3(i, 0, n) #define per1(n) per2(__i__, n) #define per(...) overload3(__VA_ARGS__, per3, per2, per1)(__VA_ARGS__) #define CP_ALL_SELECT(first, ...) first #define CP_ALL_RANGE(a) std::begin(a), std::end(a) #define all(...) CP_ALL_SELECT(__VA_OPT__(CP_ALL_RANGE, ) all)(__VA_ARGS__) #define UNIQUE(a) sort(all(a)), a.erase(unique(all(a)), a.end()), a.shrink_to_fit() #define sz(a) static_cast(a.size()) #ifndef DEBUG #define cerr \ if (false) cerr #undef endl #define endl '\n' #endif inline auto operator^=(vector::reference a, bool b) noexcept { if (b) a.flip(); return a; } inline auto operator&=(vector::reference a, bool b) noexcept { if (!b) a = false; return a; } inline auto operator|=(vector::reference a, bool b) noexcept { if (b) a = true; return a; } inline ostream &operator<<(ostream &os, __int128_t value) { ostream::sentry s(os); if (s) { __uint128_t tmp = value; if (value < 0) tmp = -tmp; char buffer[128]; char *d = std::end(buffer); do { --d; *d = "0123456789"[tmp % 10]; tmp /= 10; } while (tmp != 0); if (value < 0) --d, *d = '-'; const int len = std::end(buffer) - d; if (os.rdbuf()->sputn(d, len) != len) os.setstate(std::ios_base::badbit); } return os; } template ostream &operator<<(ostream &os, pair a) { return os << a.first << ' ' << a.second; }; template ostream &operator<<(ostream &os, vector a) { const int n = a.size(); rep(i, n) { os << a[i]; if (i + 1 != n) os << " "; } return os; } template istream &operator>>(istream &is, pair &a) { return is >> a.first >> a.second; } template ostream &operator<<(ostream &os, array a) { rep(i, n) { os << a[i]; if (i + 1 != n) os << " "; } return os; } template istream &operator>>(istream &is, vector &a) { for (T &i : a) is >> i; return is; } template bool chmin(T &x, S y) { if ((T)y < x) { x = (T)y; return true; } return false; } template bool chmax(T &x, S y) { if (x < (T)y) { x = (T)y; return true; } return false; } template void operator++(vector &a) { for (T &i : a) ++i; } template void operator--(vector &a) { for (T &i : a) --i; } template void operator++(vector &a, int) { for (T &i : a) i++; } template void operator--(vector &a, int) { for (T &i : a) i--; } void init(), solve(); int main() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); cerr << fixed << setprecision(20); init(); int t = 1; cin >> t; while (t--) solve(); } // #define COMB_MAX 1e6 // #include "lib/math/comb.hpp" // #include "lib/fps/fps.hpp" // #include "lib/math/mint.hpp" void init() {} void solve_() { int n; cin >> n; set> s; queue> q; { vec a(n); iota(all(a), 0); s.insert(a); q.push(a); } while (!q.empty()) { auto a = q.front(); q.pop(); rep(i, n - 3) { auto b = a; swap(b[i], b[i + 2]); swap(b[i + 1], b[i + 3]); if (s.contains(b)) continue; s.insert(b); q.push(b); } } cout << sz(s) << endl; for (auto &a : s) cout << a << endl; } #line 1 "lib/sequence/inversion_count.hpp" #line 10 "lib/sequence/inversion_count.hpp" #include #include #line 13 "lib/sequence/inversion_count.hpp" template> requires std::ranges::random_access_range && std::ranges::sized_range std::int64_t inversion_count(const Range &a, Compare compare = {}) { assert(std::ranges::size(a) <= std::size_t(std::numeric_limits::max())); const std::size_t n = std::ranges::size(a); auto first = std::ranges::begin(a); std::size_t ordered = 1; while (ordered < n && !compare(first[ordered], first[ordered - 1])) ++ordered; if (ordered >= n) return 0; std::int64_t equal_pairs = 0; std::size_t run = 1, reversed = 1; for (; reversed < n && !compare(first[reversed - 1], first[reversed]); ++reversed) { if (compare(first[reversed], first[reversed - 1])) run = 1; else equal_pairs += static_cast(run++); } if (reversed == n) return static_cast(n) * (n - 1) / 2 - equal_pairs; using T = std::ranges::range_value_t; constexpr bool cached = std::is_trivially_copyable_v && sizeof(T) <= 16 && std::is_default_constructible_v && std::is_copy_constructible_v && std::is_copy_assignable_v && !std::is_same_v; using Stored = std::conditional_t; std::vector current(n), buffer(n); for (std::size_t i = 0; i < n; ++i) { if constexpr (cached) current[i] = first[i]; else current[i] = static_cast(i); } auto value = [&](const Stored &x) -> decltype(auto) { if constexpr (cached) return (x); else return first[x]; }; std::int64_t result = 0; constexpr std::size_t block = 8; for (std::size_t l = 0; l < n; l += block) { const auto end = std::min(l + block, n); for (std::size_t i = l + 1; i < end; ++i) { Stored x = current[i]; std::size_t j = i; while (j > l && compare(value(x), value(current[j - 1]))) current[j] = current[j - 1], --j; current[j] = x; result += static_cast(i - j); } } for (std::size_t width = block; width < n; width *= 2) { for (std::size_t l = 0; l < n; l += 2 * width) { const auto mid = std::min(l + width, n), r = std::min(l + 2 * width, n); if (mid == r || !compare(value(current[mid]), value(current[mid - 1]))) { std::copy(current.begin() + l, current.begin() + r, buffer.begin() + l); continue; } if (compare(value(current[r - 1]), value(current[l]))) { result += static_cast(mid - l) * (r - mid); std::copy(current.begin() + mid, current.begin() + r, buffer.begin() + l); std::copy(current.begin() + l, current.begin() + mid, buffer.begin() + (l + r - mid)); continue; } std::size_t i = l, j = mid, k = l; while (i < mid && j < r) { if (compare(value(current[j]), value(current[i]))) { buffer[k++] = current[j++]; result += static_cast(mid - i); } else buffer[k++] = current[i++]; } std::copy(current.begin() + i, current.begin() + mid, buffer.begin() + k); std::copy(current.begin() + j, current.begin() + r, buffer.begin() + (k + mid - i)); } current.swap(buffer); } return result; } #line 169 "a.cpp" void solve() { string s, t; cin >> s >> t; const int n = sz(s); assert(sz(t) == n); if (s == t) { cout << "Yes" << endl; return; } if (n == 4) { swap(t[0], t[2]); swap(t[1], t[3]); if (s == t) { cout << "Yes" << endl; return; } cout << "No" << endl; return; } vec ty; rep(c, 2) { vec cnt1(26), cnt2(26); for (int i = c; i < n; i += 2) { cnt1[s[i] - 'a']++; cnt2[t[i] - 'a']++; } bool kabu = false; rep(i, 26) { if (cnt1[i] != cnt2[i]) { cout << "No" << endl; return; } kabu |= cnt1[i] >= 2; } if (kabu) continue; unordered_map mp; for (int i = c; i < n; i += 2) mp[s[i]] = sz(mp); vec pq(sz(mp)); for (int i = c; i < n; i += 2) pq[mp[t[i]]] = (i - c) / 2; ty.push_back(inversion_count(pq) % 2); } if (sz(ty) == 2 && ty[0] != ty[1]) { cout << "No" << endl; return; } cout << "Yes" << endl; return; }