Polygon Puzzle

You are given a cylindrical puzzle constructed in the shape of a regular \(n\)-gon. The puzzle consists of a center block, \(n\) edge blocks and \(n\) corner blocks. Every edge of the \(n\)-gon contains exactly 2 corner blocks and 1 edge block.

The blocks have colored faces as follows:

• An edge block has three colored faces: its top, bottom, and the outward (lateral) face. The colors on these faces might be different.
• A corner block has two outward faces. (Thus, a corner block shows colors on two faces.)
• The center block has two colored faces: its top and bottom.

The lateral side (face) corresponding to each edge of the \(n\)-gon is composed as follows. Label the corner and edge blocks in counter‐clockwise order. For the \(i\)th edge (for \(1 \le i \le n\), with the convention that the \(n+1\)th block is the first one), the lateral face is made up of:

• the counterclockwise (left) face of the \(i\)th corner block,
• the outward face of the \(i\)th edge block, and
• the clockwise (right) face of the \((i \bmod n) + 1\)th corner block.

You are allowed to perform the following operation any number of times: Choose one edge, then swap the two corner blocks on that edge and flip them vertically (so that their two lateral faces are exchanged), and also flip the edge block on that edge vertically (i.e. swap its top and bottom faces).

A face is called uniform if all its cells (pieces) are the same color. The puzzle is solved when every face (the top, bottom, and each lateral face) is uniform (note that the colors on different faces may differ).

Your task is to determine the minimum number of operations required to solve the puzzle if possible. If it is impossible, output -1.

Note: The center block remains fixed; its top and bottom colors cannot be changed.

Representation of the puzzle:

• The top face is formed by the center block's top and the top faces of all edge blocks. They must all have the same color.
• The bottom face is similarly formed by the center block's bottom and the bottom faces of all edge blocks.
• For the lateral face corresponding to edge \(i\): it consists of the counterclockwise (left) face of the \(i\)th corner block, the outward face of the \(i\)th edge block, and the clockwise (right) face of the \((i \bmod n) + 1\)th corner block. These three must share the same color.

inputFormat

The input is given in the following format:

 n
 center_top center_bottom
 (for i = 1 to n): edge_i_top edge_i_bottom edge_i_outward
 (for i = 1 to n): corner_i_left corner_i_right

Here, n is the number of sides of the polygon. The center block has top and bottom colored values. Each edge block is described by its top, bottom, and outward face colors. Each corner block is described by its two outward face colors: the first is the counterclockwise (left) face and the second is the clockwise (right) face.

outputFormat

Output a single integer representing the minimum number of operations required to solve the puzzle. If it is impossible to solve the puzzle, output -1.

sample

3
A B
A B X
A B Y
A B Z
X Z
Y X
Z Y

0