##### Canadian Computing Olympiad: 2023 Day 2, Problem 1

Finn is playing a game of "Flip it and Stick it" which is abbreviated as FiSi. FiSi is a
one-player game played on two strings, and , of `0`

s and `1`

s. Finn is allowed to make
moves of the following form:

- Select a substring of and reverse it, gluing the pieces of the string back together in their original order to form the new string .

For example, Finn may take the string `101100`

, take the substring `011`

starting at index
(assuming -based string indexing), and create the string `111000`

in one move.
Finn wins the game if does not contain as a substring. Your task is to help Finn
determine the length of the shortest winning sequence of moves or tell him that the game
cannot be won.

#### Input Specification

The first line of input contains the string .

The second line of input contains the string .

In the table below, is the first bit in , is the second bit in , and is the third bit in , when reading from left-to-right.

Marks Awarded | Bounds on |
---|---|

mark | |

marks | |

marks | |

marks | |

marks | |

marks |

#### Output Specification

Output the minimum number of moves needed or `-1`

if it is impossible to win the game.

#### Sample Input 1

```
100110
10
```

#### Sample Output 1

`2`

#### Explanation of Output for Sample Input 1

Finn starts with the string `100110`

. He cannot avoid `10`

as a substring in one move, but he
can in two moves.

For example, his first move could be to reverse the substring from index to index (`110`

)
to get `100011`

. Then, his second move can be to reverse the substring from index to index
(`1000`

) to get `000111`

, which does not have `10`

as a substring.

#### Sample Input 2

```
000
00
```

#### Sample Output 2

`-1`

#### Explanation of Output for Sample Input 2

No matter how many moves Finn makes, the string will always contain as a substring.

## Comments