#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define dbg(x) cout << #x << " " << x << endl;
#define ll long long
#define ld long double
// template<typename T>
// void pr(vector<T>& a) {
// for(auto i: a) {
// cout << i << " ";
// }
// cout << endl;
// }
void pr(vector<pair<int, int>>& a) {
for(auto i: a) {
cout << "{" << i.first << "," << i.second << "}" << " ";
}
cout << endl;
}
void pr(vector<pair<pair<int, int>, int>>& a) {
for(auto i: a) {
cout << "{ {" << i.first.first << "," << i.first.second << "}" << ", " << i.second << "} ";
}
cout << endl;
}
void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b);
const int N = 2e5 + 10;
int p1[N][3], p2[N][3];
int ac[N], ca[N];
int at[N], ta[N];
int ct[N], tc[N];
int n;
void init(std::string a, std::string b) {
n = sz(a);
map<pair<char, char>, int> mp;
for(int i = 0; i < n; i++) {
p1[i + 1][0] += p1[i][0] + (a[i] == 'A');
p1[i + 1][1] += p1[i][1] + (a[i] == 'T');
p1[i + 1][2] += p1[i][2] + (a[i] == 'C');
p2[i + 1][0] += p2[i][0] + (b[i] == 'A');
p2[i + 1][1] += p2[i][1] + (b[i] == 'T');
p2[i + 1][2] += p2[i][2] + (b[i] == 'C');
ac[i + 1] = ac[i];
ca[i + 1] = ca[i];
at[i + 1] = at[i];
ta[i + 1] = ta[i];
ct[i + 1] = ct[i];
tc[i + 1] = tc[i];
if(a[i] == 'A' && b[i] == 'C') {
ac[i + 1]++;
}
if(a[i] == 'A' && b[i] == 'T') {
at[i + 1]++;
}
if(a[i] == 'C' && b[i] == 'T') {
ct[i + 1]++;
}
if(a[i] == 'C' && b[i] == 'A') {
ca[i + 1]++;
}
if(a[i] == 'T' && b[i] == 'A') {
ta[i + 1]++;
}
if(a[i] == 'T' && b[i] == 'C') {
tc[i + 1]++;
}
}
}
int get_distance(int x, int y) {
x++, y++;
swap(x, y);
int a1 = p1[x][0] - p1[y - 1][0];
int t1 = p1[x][1] - p1[y - 1][1];
int c1 = p1[x][2] - p1[y - 1][2];
int a2 = p2[x][0] - p2[y - 1][0];
int t2 = p2[x][1] - p2[y - 1][1];
int c2 = p2[x][2] - p2[y - 1][2];
if(a1 != a2 || t1 != t2 || c1 != c2) {
return -1;
}
int answ = 0;
int tta = ta[x] - ta[y - 1];
int aat = at[x] - at[y - 1];
int mini = min(tta, aat);
tta -= mini, aat -= mini;
answ += mini;
int ttc = tc[x] - tc[y - 1];
int cct = ct[x] - ct[y - 1];
mini = min(ttc, cct);
answ += mini;
cct -= mini, ttc -= mini;
int aac = ac[x] - ac[y - 1];
int cca = ca[x] - ca[y - 1];
mini = min(aac, cca);
answ += mini;
cca -= mini, aac -= mini;
int all_sum = aat + tta + ttc + cct + aac + cca;
assert(all_sum % 3 == 0);
return answ + 2 * (all_sum / 3);
}
