The King of Byteland has an army.
The army consists of 2N soldiers.
The King has arranged the soldiers into 2 rows by N columns.
Two soldiers are neighbors if they are located next to each other in a row or in a column.
Currently, some of the soldiers are happy and some are sad.
You are given the current states of all soldiers in a String state.
For each i and j, state[i][j] is 'H' if soldier in row i, column j is happy, or 'S' if that soldier is sad.
(All indices are 0-based.)
The King knows that a happy army is a strong army, therefore he wants all his soldiers to be happy.
The soldiers can talk to other soldiers.
Whenever soldier X talks to soldier Y, soldier Y changes his state to the state of soldier X.
For example, if X is currently sad, Y becomes sad as well.
The state of soldier X does not change when X talks to Y.
You can now give some soldiers orders to talk to other soldiers.
There are three types of valid orders:
- Choose a single soldier and call him X. Choose a single neighbor of X and call him Y. X will talk to Y.
- Choose any contiguous group of soldiers in one of the rows. Each of these soldiers will talk to their neighbor in the other row.
- Choose any column A. Choose any column B adjacent to column A. Each soldier in column A will talk to their neighbor in column B.
You are given the String state.
Return the smallest non-negative integer X such that there is a sequence of X valid orders such that after the orders are executed, one after another, all the soldiers will be happy.
If there is no such sequence of orders, return -1 instead.