#nullable enable using System.Numerics; #region var (_input, _iter) = (Array.Empty(), 0); T I() where T : IParsable { while (_iter >= _input.Length) (_input, _iter) = (Console.ReadLine()!.Trim().Split(' '), 0); return T.Parse(_input[_iter++], null); } #endregion const int M = 26; bool Solve() { var s = I().Select(e => e - 'a').ToArray(); var t = I().Select(e => e - 'a').ToArray(); var n = s.Length; var (inv0, inv1) = (0L, 0L); var dup = false; for (var p = 0; p < 2; p++) { var cs = new int[M]; var ct = new int[M]; for (var i = p; i < n; i += 2) cs[s[i]]++; for (var i = p; i < n; i += 2) ct[t[i]]++; for (var i = 0; i < M; i++) if (cs[i] != ct[i]) return false; var a = new List(); var b = new List(); for (var i = p; i < n; i += 2) a.Add(s[i]); for (var i = p; i < n; i += 2) b.Add(t[i]); inv0 = FenwickTreeExtensions.InversionNumber(a, b) % 2; (inv0, inv1) = (inv1, inv0); dup |= a.Distinct().Count() != a.Count; dup |= b.Distinct().Count() != b.Count; } return dup || inv0 == inv1; } var ans = new List(); var q = I(); while (q-- > 0) ans.Add(Solve() ? "Yes" : "No"); Console.WriteLine(string.Join(Environment.NewLine, ans)); class FenwickTree where T : IAdditiveIdentity, IAdditionOperators, ISubtractionOperators { readonly T[] _values; public FenwickTree(int length) { var values = new T[length + 1]; values.AsSpan().Fill(T.AdditiveIdentity); _values = values; } public FenwickTree(IReadOnlyList data) { var values = new T[data.Count + 1]; var span = values.AsSpan(); for (var i = 1; i < span.Length; i++) span[i] = data[i - 1]; for (var i = 1; i < span.Length; i++) { var j = i + (i & -i); if (j < span.Length) values[j] += values[i]; } _values = values; } public void Add(int i, T value) { var values = _values.AsSpan(); while (i < values.Length) { values[i] += value; i += i & -i; } } public T Sum(int i) { ReadOnlySpan values = _values; var res = T.AdditiveIdentity; while (i > 0) { res += values[i]; i -= i & -i; } return res; } } // [0..N) class PointAddRangeSum // : IRangeSum> where T : IAdditiveIdentity, IAdditionOperators, ISubtractionOperators { readonly FenwickTree _data; public PointAddRangeSum(int length) => _data = new(length); public PointAddRangeSum(IReadOnlyList data) => _data = new(data); // public static PointAddRangeSum Init(IReadOnlyList data) => new(data); public void Add(int at, T value) => _data.Add(at + 1, value); public T Sum(int l, int r) => _data.Sum(r) - _data.Sum(l); // [l, r) } static class FenwickTreeExtensions { // requires PointAddRangeSum public static long InversionNumber(this IReadOnlyList a, IReadOnlyList target) where T : IComparable { List keys = [.. a, .. target]; keys = [.. keys.Distinct().Order()]; var n = keys.Count; if (n == 0) return 0; var sa = new Queue[n]; for (var i = 0; i < n; i++) sa[i] = []; for (var i = 0; i < a.Count; i++) sa[keys.BinarySearch(a[i])].Enqueue(i); var indices = new int[target.Count]; for (var i = 0; i < target.Count; i++) { var q = sa[keys.BinarySearch(target[i])]; if (q.Count == 0) return -1; indices[i] = q.Dequeue(); } return indices.InversionNumber(); } // shuffled [0..n) public static long InversionNumber(this int[] a) { var res = 0L; var n = a.Length; var data = new PointAddRangeSum(n); foreach (var i in a) { res += data.Sum(i + 1, n); data.Add(i, 1); } return res; } }