Triangulation with Distinct Edge Colors

"Everything will be in flames once red, white, and blue start running through your veins." - Slaven Bilić

Given a convex polygon with \(N\) edges where each edge is painted in one of three colors: red, white, and blue, and with vertices numbered in clockwise order from \(1\) to \(N\), your task is to find a triangulation (i.e. partition the polygon into \(N-2\) triangles using non-intersecting diagonals) such that in every triangle, the colors of the three sides are all distinct.

The polygon's boundary edges have fixed colors (provided in the input), and you are allowed to assign a color to each diagonal from the same set \(\{\text{red},\text{white},\text{blue}\}\). However, if a diagonal is shared by two triangles, it must be assigned the same color in both. In other words, for every triangle formed by the triangulation, the set of colors on its three sides (some of which come from the polygon, and some from the diagonals you color) must be exactly \(\{\text{red},\text{white},\text{blue}\}\>.

If such a triangulation exists, output YES followed by the list of diagonals (each with its assigned color). We will use a fan triangulation with vertex 1 as the common vertex. For a polygon with \(N\) vertices, the diagonals will be \((1,3), (1,4), \dots, (1, N-1)\). Note that if \(N=3\) (i.e. the polygon is already a triangle), you only need to verify that its three boundary edges are all different. If no valid triangulation exists, output -1.

inputFormat

The input begins with an integer \(T\) (the number of test cases). Each test case consists of two lines:

• The first line contains an integer \(N\) (\(3 \le N \le 10^5\)), the number of vertices of the polygon.
• The second line contains \(N\) space‐separated strings, each either red, white or blue, representing the colors of the polygon's edges in order. The first edge is between vertices 1 and 2, the second between 2 and 3, …, and the \(N\)th edge is between vertex \(N\) and 1.

outputFormat

For each test case, if a valid triangulation exists, output YES on the first line followed by \(N-3\) lines. Each of these subsequent lines should describe a diagonal in the format: u v c, where \(u\) and \(v\) (with \(u < v\)) are the endpoints of the diagonal and \(c\) is the color assigned to that diagonal. (If \(N=3\), simply output YES after verifying that the three boundary edges are all of distinct colors.)

If no valid triangulation exists, output a single line containing -1.

sample

1
3
red white blue

YES