Problem Description

There is a regular polygon with \( n \) sides, each colored with one of three colors, and its vertices are numbered from 1 to \( n \) in a clockwise order.

A triangulation of a polygon is the operation of dividing its area into a set of non-overlapping triangles, where the sides of these triangles can be the sides of the polygon or its internal diagonals. In this task, each diagonal used for the polygon's triangulation is also colored with one of three colors.

A triangulation is considered "very good" if all \( n - 2 \) triangles have all three sides of different colors.

Your task is to determine if a given polygon with diagonals is properly triangulated and if this triangulation is "very good".

Input Format

The input consists of \( n \) lines.

• The first line contains a positive integer \( T \), indicating the Subtask number.
• The second line contains a positive integer \( n \), as described in the Problem Description.
• The third line contains a \( n \)-digit positive integer, representing the colors of the polygon's sides. Specifically, the first digit represents the color of the side \((1, 2)\), the second digit represents the color of the side \((2, 3)\), and the \( i \)-th digit represents the color of the side \((i, i+1)\). Notably, the \( n \)-th digit represents the color of the side \((n, 1)\). Colors are represented by the digits 1, 2, and 3.
• The next \( n-3 \) lines each contain a description of a diagonal in the format x y c, where \( x \) and \( y \) are the polygon's vertices, and \( c \) is the color of the diagonal. The data guarantees that vertices \( x \) and \( y \) are neither equal nor adjacent.

Output Format

The output consists of one line.

• If the input polygon is not correctly triangulated, output neispravna triangulacija.
• If the input polygon is correctly triangulated but the triangulation is not good, output neispravno bojenje.
• Otherwise, output tocno.

Sample Input and Output

Sample Input #1

1
5
12113
1 3 3
2 5 2

Sample Output #1

neispravna triangulacija

Sample Input #2

1
4
1212
1 3 2

Sample Output #2

neispravno bojenje

Sample Input #3

1
7
1223121
1 3 3
3 5 1
5 7 3
7 3 2

Sample Output #3

tocno

Notes

Data Size and Constraints

This problem uses bundled testing.

Notably, for \( 100\% \) of the data, \( 1 \le T \le 5 \).

Notes

This problem's score is set according to the original COCI, with a full score of 110.

Translated from COCI2019-2020 CONTEST #2 T3 Checker.

见题面 Input 部分

见题面 Output 部分