E - Replace Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

正整数 N および、英小文字からなる長さ N の文字列 S,T が与えられます。

以下の操作を繰り返し（0 回でも良い）行うことで、S を T と一致させることが可能かどうか判定してください。 可能な場合は、そのために必要な操作回数の最小値も求めてください。

  • 英小文字 x,y を選び、S に含まれる 全て の x をそれぞれ y で置き換える。

制約

  • 1\leq N \leq 2\times 10^5
  • N は整数
  • S,T はそれぞれ英小文字からなる長さ N の文字列

入力

入力は以下の形式で標準入力から与えられる。

N
S
T

出力

S を T と一致させることが可能ならばそのために必要な操作回数の最小値を、不可能ならば -1 を出力せよ。

入力例 1

6
afbfda
bkckbb

出力例 1

4

以下のように操作を 4 回行うことで、S を T と一致させることができます。

  1. x= b, y= c として操作を行う。S= afcfda となる。
  2. x= a, y= b として操作を行う。S= bfcfdb となる。
  3. x= f, y= k として操作を行う。S= bkckdb となる。
  4. x= d, y= b として操作を行う。S= bkckbb となり、T と一致する。

3 回以下の操作で S を T と一致させることはできないため、必要な操作回数の最小値は 4 です。

入力例 2

4
abac
abac

出力例 2

0

S と T が既に一致しているため、操作を行う必要はありません。

入力例 3

4
abac
abrc

出力例 3

-1

どのように操作を繰り返し行っても、S を T と一致させることはできません。

入力例 4

4
abac
bcba

出力例 4

4

Score : 500 points

Problem Statement

You are given a positive integer N and two strings S and T, each of length N and consisting of lowercase English letters.

Determine whether it is possible to make S identical to T by repeating the operation below any number of times (possibly zero). If it is possible, also find the minimum number of operations required.

  • Choose two lowercase English letters x, y and replace every occurrence of x in S with y.

Constraints

  • 1\leq N \leq 2\times 10^5
  • N is an integer.
  • Each of S and T is a string of length N, consisting of lowercase English letters.

Input

The input is given from Standard Input in the following format:

N
S
T

Output

If it is possible to make S identical to T, print the minimum number of operations required. Otherwise, print -1.

Sample Input 1

6
afbfda
bkckbb

Sample Output 1

4

By performing the operation four times in the following way, you can make S identical to T:

  1. Choose x= b and y= c. S becomes afcfda.
  2. Choose x= a and y= b. S becomes bfcfdb.
  3. Choose x= f and y= k. S becomes bkckdb.
  4. Choose x= d and y= b. S becomes bkckbb, which is identical to T.

It cannot be done with fewer than four operations, so the minimum number of operations required is 4.

Sample Input 2

4
abac
abac

Sample Output 2

0

S and T are already identical, so no operations are required.

Sample Input 3

4
abac
abrc

Sample Output 3

-1

No matter how you repeat the operation, it is impossible to make S identical to T.

Sample Input 4

4
abac
bcba

Sample Output 4

4