P16328 Nocturne

 在旅程的尽头，那些本不属于我们的，已物归原主。

You are given two strings $s$ and $t$ of length $n$, indexed from $1$. In one operation, you may freely choose a **non-decreasing** integer sequence $p$ of length $n$ with values in $[1,n]$, satisfying $|p_i-i|\le 1$. Then, simultaneously, set all $s_i\gets s_{p_i}$. Find the minimum number of operations needed to transform $s$ into $t$. If it is impossible, output $-1$.

This problem contains multiple test cases. The first line contains a positive integer $T$, the number of test cases. Then for each test case, the first line contains the string $s$, and the second line contains the string $t$.

For each test case, output one integer per line, the answer.

#### Sample Explanation For the first test case, we can transform $s$ into $t$ as follows: $$\texttt{aabbccc}\to\texttt{abbbbcc}\to\texttt{abbbbbc}$$ The corresponding sequences $p$ for the two operations are $[1,3,4,4,4,5,6]$ and $[1,2,3,4,5,5,7]$. It is impossible to do this in a single operation, so the answer is $2$. #### Constraints Let $m$ denote the size of the alphabet, that is, the strings only contain the first $m$ lowercase English letters. | $\text{Subtask}$ | $n,\sum n\le$ | $m\le$ | Special Property | $\text{Score}$ | | :--------------: | :------------: | :----: | :--------------: | :------------: | | $1$ | $20$ | $2$ | A | $15$ | | $2$ | $5\times 10^3$ | ^ | None | $30$ | | $3$ | $10^6$ | $26$ | B | $25$ | | $4$ | ^ | ^ | None | $30$ | - Special Property A: It is guaranteed that $s_i\le s_{i+1}$ and $t_i\le t_{i+1}$. - Special Property B: It is guaranteed that $t$ only contains the character `a`. For all data, it is guaranteed that $1\le T\le 5\times 10^3$, $1\le n,\sum n\le 10^6$, the strings contain only lowercase English letters, and $|s|=|t|$.