Description

kkke is playing a flip game on an $n \times n$ board. Each cell of the board contains a piece, and each piece has $2$ faces: one black and one white. Initially, some pieces face up black and others face up white. Now kkke wants to make all pieces face the same color (either all black up or all white up) with the minimum number of flips. Each time a flip is performed, kkke may choose any piece to flip; at the same time, the $4$ pieces that are respectively adjacent to it up, down, left, and right must also be flipped.

Input Format

The first line contains an integer $n$, indicating the board size is $n \times n$.

Then follow $n$ lines, each containing $n$ letters, representing the initial state of the board. If a letter is $\tt w$, the corresponding piece is currently white side up; if it is $\tt b$, the piece is currently black side up.

Output Format

Output one line. If it is impossible to reach the target state, output Impossible; otherwise, output a single integer, the minimum number of flips kkke needs.

4
bwwb
bbwb
bwwb
bwww

4

Hint

• Constraints
  • For $30\%$ of the testdata, $1 \le n \le 4$.
  • For $100\%$ of the testdata, $1 \le n \le 16$.

Translated by ChatGPT 5