Background

After failing several times, the little frog’s way of thinking began to change.

It began to search for what makes it a frog.

It began to look for help from other frogs.

It is undergoing a transformation.

It is being refined.

It will become light!

It gave itself a new name — Frog Cyan (qwq), because the name is very cute.

Problem Description

White light can be split into cyan light and many other colors of light.

$\{a\}$ is a sequence of length $n$ with $k$ different colors. The color of the $i$-th element is $a_i$ (it is guaranteed that colors $1\sim k$ all appear in $a$).

$\{b\}$ is a sequence of length $m$. The color of the $i$-th element is $b_i$ (it is guaranteed that each $b_i$ is one of the $k$ colors, but it is not guaranteed that all $k$ colors appear in $b$). We may change the colors at some positions in $b$ and obtain a sequence $b'$ that still has length $m$.

For $b'$ and $a$, connect every pair of positions with the same color by a line segment of that color.

For example, when $n=3,m=4,k=3,a=\{1,2,3\},b'=\{1,3,2,2\}$, the connections look like this:

You are required that line segments of different colors do not intersect each other, and all $k$ colors must appear in $b$. What is the minimum number of modifications?

Formally, let the modified valid sequence be $b'$. You need to minimize:

In the above case $a=\{1,2,3\},b'=\{1,3,2,2\}$, the connections have an intersection (between the red $2$ and the purple $3$).

But if we modify $b$ to $\{1,2,3,3\}$, then the connections do not intersect and the conditions are satisfied:

Note:

• For $b' = \{1,1,4,5\}$, the connections also do not intersect, but $b'$ contains colors outside the $k$ colors (there are $4$ and $5$), so this $b'$ is invalid.
• For $b' = \{1,1,1,1\}$, the connections also do not intersect, but $b'$ does not contain all colors in $1\sim k$ (it lacks $2$ and $3$), so this $b'$ is also invalid.

In particular, if no matter how you modify it you still cannot satisfy the requirements, output -1.

Input Format

The first line contains two integers $n,m$, representing the number of elements in sequences $a,b$ respectively.

The second line contains $n$ integers, where the $i$-th integer denotes $a_i$.

The third line contains $m$ integers, where the $i$-th integer denotes $b_i$.

Output Format

One line with one integer, representing the minimum number of modifications required to satisfy the conditions.

If no matter how you modify it you still cannot satisfy the requirements, output -1.

3 4
1 2 3
1 3 2 2

2

5 5
1 2 3 4 4
1 2 3 3 3

1

5 10
1 2 3 4 5
1 2 2 3 2 2 2 4 5 4

3

10 2
1 2 1 2 2 2 2 2 2 2
2 2

-1

Hint

[Sample #1 Explanation]

Modify $\{1,3,2,2\}$ into $\{1,2,2,3\}$.

It can be proven that this uses the minimum number of modifications.

[Sample #2 Explanation]

Modify $\{1,2,3,3,3\}$ into $\{1,2,3,3,4\}$.

It can be proven that this uses the minimum number of modifications.

This problem enables bundled test and subtask dependencies.

Time limit: 2 s.

• For $100\%$ of the testdata, it is guaranteed that $1\le n,m\le 2\times 10^6$, $1\le a_i,b_i \le n$. Let $\max\limits_{i=1}^n{a_i} = k$. It is guaranteed that $1\sim k$ all appear in $a$, and $1\le k \le n$.

Translated by ChatGPT 5