Pseudoknot

An RNA strand is written here as a string of uppercase letters. When a strand folds, two reversed pairs of segments can cross each other, and that shape is called a pseudoknot. Finding the pseudoknot with the longest links is one step in the analysis of a new strand, because longer links mean a more stable structure.

A string $w$ is a pseudoknot if it can be cut into six consecutive parts

$w = u\,v\,z^R\,u^R\,y\,z$

where $u^R$ and $z^R$ are the reversals of $u$ and $z$. Here $|u| \ge 1$ and $|z| \ge 1$, while $v$ and $y$ may be empty. The pair $(u, u^R)$ is one link and the pair $(z, z^R)$ is the other.

For example, ICPCINAEROKCPCIFORKOREA is a pseudoknot, with $u$ = ICPC, $v$ = IN, $z^R$ = AEROK, $u^R$ = CPCI, $y$ = FOR, and $z$ = KOREA. The string AQQQQRRRRRQQQQQ is not a pseudoknot, because no cut of it has that form.

Figure 1. A pseudoknot (a) and a string that is not a pseudoknot (b)

In ICPCAEROKCPCIKOREA both $v$ and $y$ are empty, and the string is still a pseudoknot. Only $u$ and $z$ have to be non-empty.

Figure 2. A pseudoknot whose $v$ and $y$ are empty

One string can have several pseudoknot structures. ICPCINAEROKCPCIAECIKOREA can be cut as $u$ = ICPC, $v$ = IN, $z^R$ = AEROK, $u^R$ = CPCI, $y$ = AECI, $z$ = KOREA, and it can also be cut as $u$ = IC, $v$ = PCINAEROKCPCI, $z^R$ = AE, $u^R$ = CI, $y$ = KOR, $z$ = EA. The first cut has the longer links, so it is the one to report.

Figure 3. Two pseudoknot structures for the same string

Your program reads from standard input. The input is one string over the uppercase alphabet, with no whitespace and no line break inside it. The length of the string is between 1 and 200,000.

Your program writes to standard output. Print one line holding the largest integer $t$ such that the input string $w$ can be cut as $w = u\,v\,z^R\,u^R\,y\,z$ with $|u| \ge t$, $|z| \ge t$, $|v| \ge 0$, and $|y| \ge 0$. If no such $t$ exists, that is, if $w$ is not a pseudoknot, print -1 instead.