Problem Statement

Given a string, the reversal operation r(i, j) reverses the substring of the string from the i-th character to the j-th character (0-indexed, inclusive). A reversal chain is a sequence of reversals where the range of each reversal is included in the range of the previous reversal. Formally, the sequence r(i₁, j₁), r(i₂, j₂), ..., r(i_m, j_m) is a reversal chain if i₁ <= i₂ <= ... <= i_m, and j₁ >= j₂ >= ... >= j_m.

You are given a string init which contains only '0' (zero) and '1' (one) characters. You want to transform this string into the string goal using a reversal chain. Return the minimum possible length of a reversal chain that transforms init into goal. Return -1 if it is impossible.

Definition

Constraints

Examples