#pragma GCC optimize("Ofast") #include #define rep(i,n) for(ll i=0;i<(ll)(n);i++) #define rep_r(i,n) for(ll i=(ll)(n)-1;i>=0;i--) #define rep2(i,sta,n) for(ll i=sta;i<(ll)(n);i++) #define rep2_r(i,sta,n) for(ll i=(ll)(n)-1;i>=sta;i--) #define all(v) (v).begin(),(v).end() #define rall(v) (v).rbegin(),(v).rend() #define vlin(name,sz,offset) vl name(sz); rep(i,sz){cin>>name[i]; name[i]-=offset;} #define pb push_back #define mp make_pair #define fi first #define se second using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair P; typedef pair LP; typedef map LM; typedef tuple LT; typedef tuple LT4; typedef vector vi; typedef vector vvi; typedef vector vl; typedef vector vvl; typedef vector v3l; typedef vector v4l; typedef vector v5l; typedef vector vlp; typedef vector vvlp; typedef vector vlt; typedef vector vvlt; typedef vector vs; typedef vector vvs; typedef vector vd; typedef vector vvd; typedef vector vb; typedef vector vvb; template class infinity{ public: static constexpr T MAX=numeric_limits::max(); static constexpr T MIN=numeric_limits::min(); static constexpr T val=numeric_limits::max()/2-1e6; static constexpr T mval=numeric_limits::min()/2+1e6; }; const int INF = infinity::val; const ll LINF = infinity::val; const ld DINF = infinity::val; struct RandGen { using ud = uniform_int_distribution; mt19937 mt; RandGen() : mt(chrono::steady_clock::now().time_since_epoch().count()) {} ll l(ll a, ll b) { ud d(a, b - 1); return d(mt); } LP lp(ll a, ll b, bool rng = true) { ll x = l(a, b - 1), y = l(rng ? x + 1 : a, b - 1); return {x, y}; } vl vecl(ll n, ll a, ll b) { ud d(a, b - 1); vl ret(n); rep(i, n) ret[i] = d(mt); return ret; } vl vecperm(ll n, ll from = 0) { vl perm(n); iota(all(perm), from); shuffle(perm); return perm; } string str(ll n, string op) { vl fig = vecl(n, 0, op.size()); string s; rep(i, n) s.pb(op[fig[i]]); return s; } string straz(ll n, ll a = 0, ll z = 26) { vl az = vecl(n, a, z); string s; rep(i, n) s.pb('a' + az[i]); return s; } string strnum(ll n, ll zero = 0, ll ten = 10) { vl zt = vecl(n, zero, ten); string s; rep(i, n) s.pb('0' + zt[i]); return s; } void shuffle(vl &a) { std::shuffle(all(a), mt); } }; #define dout cout template struct is_specialize:false_type{}; template struct is_specialize::type>:true_type{}; template struct is_specialize::type>:true_type{}; template struct is_specialize::value, void>>:true_type{}; void dump(const char &t) { dout<::value, nullptr_t> =nullptr> void dump(const T&t) { dout< void dump(const T&t, enable_if_t::value>* =nullptr) { string tmp;if(t==infinity::val||t==infinity::MAX)tmp="inf";if(is_signed::value&&(t==infinity::mval||t==infinity::MIN))tmp="-inf";if(tmp.empty())tmp=to_string(t);dout< void dump(const pair&); template void dump(const T&t, enable_if_t::value>* =nullptr) { dout << "{ "; for(auto it=t.begin();it!=t.end();){ dump(*it); dout << (++it==t.end() ? "" : " "); } dout<<" }"; } template void dump(const pair&t) { dout<<"("; dump(t.first); dout<<" "; dump(t.second); dout << ")"; } void trace() { dout << "\n"; } template void trace(Head&&head, Tail&&... tail) { dump(head); if(sizeof...(tail)) dout<<", "; trace(forward(tail)...); } #ifdef ONLINE_JUDGE #define debug(...) (void(0)) #else #define debug(...) do {dout<<#__VA_ARGS__<<" = ";trace(__VA_ARGS__); } while(0) #endif template void coutarray(vector& v, int offset = 0, string sep = " ") { rep(i, v.size()) { if (i > 0) cout << sep; if (offset) cout << v[i] + offset; else cout << v[i]; } cout << "\n"; } template void coutmatrix(vector>& v, int offset = 0) { rep(i, v.size()) { coutarray(v[i], offset); } } template void coutbin(T &a, int d) { for (int i = d - 1; i >= 0; i--) cout << ((a >> i) & (T)1); cout << "\n"; } template void iquery(initializer_list q, A &a, string str = "? ") { cout << str; vector v(q); coutarray(v); cout.flush(); cin >> a; } // template void iquery(initializer_list q, A &a, string str = "? ") { vector query(q); RandGen rg; // a = query[0] ? A() : A(); // } template void ianswer(A a, string str = "! ") { cout << str << a << "\n"; cout.flush(); } int ceil_pow2(ll n) { int x = 0; while ((1ULL << x) < (unsigned long long)(n)) x++; return x; } int floor_pow2(ll n) { int x = 0; while ((1ULL << (x + 1)) <= (unsigned long long)(n)) x++; return x; } ll POW(__uint128_t x, int n) { assert(n >= 0); ll res = 1; for(; n; n >>= 1, x *= x) if(n & 1) res *= x; return res; } ll sqrt_ceil(ll x) { ll l = -1, r = x; while (r - l > 1) { ll m = (l + r) / 2; if (m * m >= x) r = m; else l = m; } return r; } template ll digits(T n) { assert(n >= 0); ll ret = 0; while(n > 0) { ret++; n /= 10; } return ret; } template T ceil(T x, S y) { assert(y); return (y < 0 ? ceil(-x, -y) : (x > 0 ? (x + y - 1) / y : x / y)); } template T floor(T x, S y) { assert(y); return (y < 0 ? floor(-x, -y) : (x > 0 ? x / y : (x - y + 1) / y)); } template void uniq(vector&a) { sort(all(a)); a.erase(unique(all(a)), a.end()); } template void comp(vector&a) { vector b = a; uniq(b); rep(i, a.size()) a[i] = lower_bound(all(b), a[i]) - b.begin(); } template bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1;} return 0; } template bool chmax(T &a, const T &b) { if (b > a) { a = b; return 1;} return 0; } template int lbs(vector &a, const T &b) { return lower_bound(all(a), b) - a.begin(); }; template int ubs(vector &a, const T &b) { return upper_bound(all(a), b) - a.begin(); }; ll binary_search(function check, ll ok, ll ng) { assert(check(ok)); while (abs(ok - ng) > 1) { auto x = (ng + ok) / 2; if (check(x)) ok = x; else ng = x; } return ok; } template vector csum(vector &a) { vl ret(a.size() + 1, 0); rep(i, a.size()) ret[i + 1] = ret[i] + a[i]; return ret; } template vector> RLE(const vector &v) { vector> res; for(auto &e : v) if(res.empty() or res.back().first != e) res.emplace_back(e, 1); else res.back().second++; return res; } vector> RLE(const string &v) { vector> res; for(auto &e : v) if(res.empty() or res.back().first != e) res.emplace_back(e, 1); else res.back().second++; return res; } const string drul = "DRUL"; vl dx = {1, 0, -1, 0}; vl dy = {0, 1, 0, -1}; ll solve(ll n, vl a) { ll ans = n - a[0]; return ans; } ll naive(ll n, vl a) { ll ans = n + a[0]; return ans; } void compare(bool check = true) { RandGen rg; ll c = 0, loop = 10; while (++c) { if (c % loop == 0) cout << "reached " << c / loop << "loop" << "\n", cout.flush(); ll n = 10; vl a = rg.vecl(n, 1, 1e2); auto so = solve(n, a); auto na = naive(n, a); if (!check || na != so) { cout << c << "times tried" << "\n"; debug(n, a); debug(so); debug(na); if (check || (!check && c > loop)) break; } } } stack> merge(vector> rl) { stack> st; for (auto [c, cnt]: rl) { if (st.size() && st.top().fi == c) { auto [_, cnt2] = st.top(); st.pop(); st.push({c, cnt + cnt2}); } else if (st.size() > 1) { auto [_, cnt2] = st.top(); if (cnt2 & 1) { st.pop(); auto [_, cnt3] = st.top(); st.pop(); st.push({c, cnt + cnt2 + cnt3}); } else st.push({c, cnt}); } else { st.push({c, cnt}); } } return st; } void solve() { ll n; cin >> n; string s, t; cin >> s >> t; auto srl = RLE(s); auto trl = RLE(t); auto sst = merge(srl); auto tst = merge(trl); if (sst.size() != tst.size()) { cout << -1 << "\n"; return; } while (sst.size()) { auto [c, cnt] = sst.top(); sst.pop(); auto [c2, cnt2] = tst.top(); tst.pop(); if (c != c2 || (cnt & 1) != (cnt2 & 1)) { cout << -1 << "\n"; return; } } ll ans = 0; rep(i, n) { if (s[i] != t[i]) ans++; } cout << ans << "\n"; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cout << fixed << setprecision(15); int t = 1; //cin >> t; while (t--) solve(); // while (t--) compare(); }