Codeforces Round 501 (Div. 3) |
---|
Finished |
You are given two strings $$$s$$$ and $$$t$$$. Both strings have length $$$n$$$ and consist of lowercase Latin letters. The characters in the strings are numbered from $$$1$$$ to $$$n$$$.
You can successively perform the following move any number of times (possibly, zero):
You can't apply a move to the string $$$t$$$. The moves are applied to the string $$$s$$$ one after another.
Your task is to obtain the string $$$t$$$ from the string $$$s$$$. Find any way to do it with at most $$$10^4$$$ such moves.
You do not have to minimize the number of moves, just find any sequence of moves of length $$$10^4$$$ or less to transform $$$s$$$ into $$$t$$$.
The first line of the input contains one integer $$$n$$$ ($$$1 \le n \le 50$$$) — the length of strings $$$s$$$ and $$$t$$$.
The second line of the input contains the string $$$s$$$ consisting of $$$n$$$ lowercase Latin letters.
The third line of the input contains the string $$$t$$$ consisting of $$$n$$$ lowercase Latin letters.
If it is impossible to obtain the string $$$t$$$ using moves, print "-1".
Otherwise in the first line print one integer $$$k$$$ — the number of moves to transform $$$s$$$ to $$$t$$$. Note that $$$k$$$ must be an integer number between $$$0$$$ and $$$10^4$$$ inclusive.
In the second line print $$$k$$$ integers $$$c_j$$$ ($$$1 \le c_j < n$$$), where $$$c_j$$$ means that on the $$$j$$$-th move you swap characters $$$s_{c_j}$$$ and $$$s_{c_j + 1}$$$.
If you do not need to apply any moves, print a single integer $$$0$$$ in the first line and either leave the second line empty or do not print it at all.
6
abcdef
abdfec
4
3 5 4 5
4
abcd
accd
-1
In the first example the string $$$s$$$ changes as follows: "abcdef" $$$\rightarrow$$$ "abdcef" $$$\rightarrow$$$ "abdcfe" $$$\rightarrow$$$ "abdfce" $$$\rightarrow$$$ "abdfec".
In the second example there is no way to transform the string $$$s$$$ into the string $$$t$$$ through any allowed moves.
Name |
---|