Problem Description

You have a cylindrical jigsaw puzzle whose shape is a regular $n$-gon. It is made of one center piece, $n$ edge pieces, and $n$ corner pieces. On each side of the regular $n$-gon, there are two corner pieces and one edge piece. (The figure below shows the top view when $n=5$. Blue pieces are corner pieces, red pieces are edge pieces, and the gray piece is the center piece.)

Each edge piece has colors on three faces in total: the top face, the bottom face, and the outward exposed side face. The colors on these faces are not necessarily the same. Each corner piece has two outward exposed side faces, so it has colors on four faces in total, and the colors are also not necessarily the same. The center piece has colors only on the top and bottom faces.

We number the corner pieces and edge pieces counterclockwise. The side surface of the $i$-th side $(i<n)$ of the regular $n$-gon is formed by the counterclockwise-direction side face of the $i$-th corner piece, the side face of the $i$-th edge piece, and the clockwise-direction side face of the $(i+1)$-th corner piece. In particular, the side surface of the $n$-th side is formed by the counterclockwise-direction side face of the $n$-th corner piece, the side face of the $n$-th edge piece, and the clockwise-direction side face of the $1$-st corner piece.

Then, you can perform the following operation: choose one side of the puzzle, swap the two corner pieces on that side and flip them upside down (note that the two side faces will be swapped), and also flip the edge piece on that side upside down.

We say a face is neat if and only if all colors on that face are the same. Now you need to perform some operations to make every face of this puzzle neat.

Input Format

The first line contains a positive integer $n$.

The next line contains two integers $col_{tp},col_{bt}$, representing the colors of the top and bottom faces of the center piece, respectively.

The next $n$ lines each contain four integers $ct_i,cl_i,cr_i,cb_i$, representing the color of the top face, the counterclockwise-direction side face, the clockwise-direction side face, and the bottom face of the $i$-th corner piece, respectively.

The next $n$ lines each contain three integers $et_i,es_i,eb_i$, representing the color of the top face, the side face, and the bottom face of the $i$-th edge piece, respectively.

Output Format

If there is no solution, output $-1$.

Otherwise, first output one line with an integer $m$, the number of operations. Then output one line with $m$ integers, where the $i$-th integer is the side index chosen in the $i$-th operation.

You need to ensure that the number of operations does not exceed $100000$. If there are multiple solutions, output any one.

4
0
5
5 4 3 0
0 1 2 5
0 2 3 5
5 1 4 0
0 1 5
0 2 5
5 3 0
0 4 5

5
1 2 3 2 1

Hint

Sample Explanation

As shown in the figure below.

Constraints

For $100\%$ of the testdata, it is guaranteed that $4\leq n \leq 100$, $0\leq ct_i,cl_i,cr_i,cb_i\leq n+1$, and $\{es_1,es_2,...,es_n,col_{tp},col_{bt}\}$ forms a permutation of $0\sim n+1$.

Notes

Translated from AGM 2022 Qualification Round F Kube。

Translated by ChatGPT 5