time limit per test: 0.25
memory limit per test: 4096
A new kind of elementary particles was discovered in recent physical experiments. These particles were named "buons". It was also discovered that there exist two types of buons, which were named "Y+" (psi +) and "Y-" (psi -) buons. It became known that buons tend to form chains. Moreover, a very interesting property of buons, named "going through", was discovered: if two buons with different types are neighbors in a chain, they can easily exchange places one with other.
Because one "going through" takes very short time, the order of buons in chain can quickly change. Now the physicists are interested, how many "goings through" must happen for one chain to become other.
You are to help them. Write a program, which determines the minimal number of "goings through" which will allow one chain to become other.
First two lines of input contains strings of "+" and "-" characters, describing first and second buon chains. The "+" character stands for Y+ buon, and "-" character stands for Y- buon. The length of each string doesn't exceed 5000; moreover, there is at leat one buon in each chain.
If it is possible to make the second chain from the first, using only "goings trough", write on the first line of output the minimal number K of "goings through" which are required. If it is impossible to make the secong chain from the first, output only integer "-1".
|Author:||NNSU #2 team
|Resource:||Compiled from many sources
|Server time: 2017-09-23 04:01:59||Online Contester Team © 2002 - 2016. All rights reserved.|