P10395 Frog Looking for Cyan.

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.

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: $$ \sum_{i=1}^{m}[b_i\ne b'_i] $$ 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`.

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$.

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`.

**[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.** |$\text{Subtask}$| $n,m\le$ | Score | Dependencies | |:---:|:---:|:---:|:---:| | $1$ | $5$ | $5$ | None | | $2$ | $5000$| $35$ | $1$ | | $3$ | $10^5$| $30$ | $1,2$ | | $4$ | $2\times 10^6$| $30$ | $1,2,3$ | - 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