This problem requires careful consideration of case distinctions. In this editorial, \(X_i\) denotes the \(i\)-th character of a string \(X\).

First, if there exist a pair \(i,j\ (i\neq j)\) such that \(S_i=S_j\) and \(T_i\neq T_j\), then the answer is \(-1\), because no operation makes two same characters different.

From now on, we will eliminate such cases and assume that \(S_i=S_j \Rightarrow T_i=T_j\) for all \(i\) and \(j\).

Then, we can consider the following directed graph \(G\):

• The vertex set of \(S\) has \(26\) vertices, labeled with lowercase English letters a, b, …, z.
• \(G\) has an edge \(x\rightarrow y\) if and only if there exists \(i\ (1\leq i\leq N)\) such that \(S_i=x\) and \(T_i=y\).

By the property “\(S_i=S_j \Rightarrow T_i=T_j\) for all \(i\) and \(j\),” we see that the outdegree of every vertex is \(0\) or \(1\).

Moreover, consider placing pieces on some of the vertices on \(G\). Initially, vertex \(c\) has a piece on it if there exists \(i\) with \(S_i=c\) (\(\Leftrightarrow\) if the outdegree of \(c\) is \(1\)), and no piece otherwise.

The following is an example of \(G\). For instance, \(S=\) bcdefghij and \(T=\) aaccghfgg turns into the following graph. There are also isolated vertices k, l, …, z, but they are omitted. Red squares represent pieces.

Using the concept of this graph and pieces, the problem can be rephrased as follows.

• You are given a graph \(G\) and initial positions of pieces. Each piece has a destination, which coincides with the vertex that the only edge going from the piece’s current vertex is pointing at. We want to make every piece located at its destination by repeating the following operation. Is it possible to do so? If it is possible, how many operations are required at minimum?
  • Operation: choose two vertices \(x\) and \(y\) (\(x \neq y\)), and move all the pieces on vertex \(x\) to vertex \(y\).

The key to solving this problem is that, once multiple pieces are placed on the same vertex, they never end up at different vertices. In other words, we may not place pieces with different destinations at the same vertex. How can we move the pieces subject to this constraint?

Let us consider the initial graph \(G\) and placements of the pieces. Each connected component is classified into one of the following six types:

• A: an isolated vertex
• B: a cycle of length \(1\)
• C: a cycle of length \(2\) or greater
• D: a rooted tree
• E: a cycle of length \(1\), and a rooted tree rooted at the cycle
• F: a cycle of length \(2\) or greater, and rooted trees connected to the vertices in the cycle

To come to the conclusion first, the answer is as follows.

• If \(B\) consists of zero or more type-B connected components and one or more type-C connected components, the answer is \(-1\).
• Otherwise, the answer is the number of pieces whose destinations are different from their original vertex, plus the number of connected components of type C. That is, the answer is \(N-(a+b+d+e)+c\), where \(x\) denotes the number of connected components of type \(c\).

For the former case, “\(G\) consists of zero or more type-B connected components and one or more type-C connected components” if and only if “\((A_a,A_b,\dots,A_z)\) is a permutation of \((A_a,A_b,\dots,A_z)\), and \(S\neq T\),” where \(A_c\) is the vertex that the edge going from vertex \(c\) is pointed at (or \(-1\) if such an edge does not exist). For the latter case, in order to find the number of connected components of type C, it is sufficient to count the connected components of size two or greater where the indegree of every vertex is at most \(1\). Since \(G\) has no greater than \(26\) vertices, almost any solution will pass as long as it runs in polynomial time.

Lastly, we demonstrate a rough proof.

The former case is justified because, any operation performed for the first time will make tow pieces with different destination gather at the same vertex.

For the second case, we can prove that the value is a lower bound as follows: any piece whose destination is different from its initial vertex requires at least one operation, and one cannot move all the pieces in a type-C connected component to their destinations in the same number of operations than the number of pieces (intuitively, at least one piece must evacuate to another vertex).

For the second case, we can prove that the value is a upper bound by actually constructing the procedure. First, for each connected component of type A, B, D, and E, move each piece to its destination, in root-to-leaf order. For a type-F connected component, one can pick an arbitrary vertex in the cycle to another vertex that is not contained in the cycle and that has a piece whose destination is same as that of the original piece, in order to boil down to type-D case. Finally, for type C, one can move one arbitrary piece to an empty vertex that has been spared by processing type-A, D, E, and F connected components, in order to reduce to type-D case.

Sample code (C++):

#include <bits/stdc++.h>
#include <atcoder/dsu>

using namespace std;
using namespace atcoder;

const int C = 26;

int main() {
    int n;
    cin >> n;
    string s, t;
    cin >> s >> t;
    if (s == t) {
        cout << 0 << endl;
        return 0;
    }
    vector<int> to(C, -1);
    for (int i = 0; i < n; i++) {
        int sc = s[i] - 'a';
        int tc = t[i] - 'a';
        if (to[sc] != -1 and to[sc] != tc) {
            cout << -1 << endl;
            return 0;
        }
        to[sc] = tc;
    }
    bool is_perm = true;
    vector<int> tmp = to;
    sort(tmp.begin(), tmp.end());
    for (int i = 0; i < C; i++) {
        is_perm &= (tmp[i] == i);
    }
    if (is_perm) {
        cout << -1 << endl;
        return 0;
    }
    int ans = 0;
    vector<int> in_deg(C);
    dsu uf(C);
    for (int i = 0; i < C; i++) {
        if (to[i] != -1) {
            if (to[i] != i) {
                ans++;
            }
            in_deg[to[i]]++;
            uf.merge(i, to[i]);
        }
    }
    vector<vector<int>> groups = uf.groups();
    for (const vector<int> &g: groups) {
        bool is_cycle = true;
        for (int i: g) {
            is_cycle &= (in_deg[i] == 1);
        }
        if (is_cycle and g.size() > 1) {
            ans++;
        }
    }
    cout << ans << endl;
}