P14730 [ICPC 2022 Seoul R] Palindrome Type

A **palindrome** string is a word which reads the same backward as forward, such as $\text{madam}$ or $\text{racecar}$. In this problem we only consider strings with lowercase alphabets. We newly define the types of palindromes. If a string is not a palindrome, we try to make it a palindrome by removing the minimum number of characters in the string. For a string $w$, if $k$ is the minimum number of characters removed to make the string a palindrome, we call the string $w$ a **type-$k$ palindrome**. Thus, if $w$ is a palindrome, then $w$ is a type-0 palindrome. Given a string $w$, write a program to determine if $w$ is a type-$k$ palindrome where $k = 0, 1, 2, 3$.

Your program is to read from standard input. The input is a single line containing a string $w$ with length $n$ ($5 \leq n \leq 10^5$) of lowercase alphabets.

Your program is to write to standard output. Print exactly one line. The line should contain a number $k$ among $\{0, 1, 2, 3, -1\}$ if the input string is a type-$k$ palindrome where $k = 0, 1, 2, 3$ and otherwise $-1$. The negative number $-1$ means the input string is not a type-$k$ palindrome where $k = 0, 1, 2, 3$.