Description

There is a regular polygon whose $n$ sides are colored using one of three colors, and its vertices are labeled from $1$ to $n$ in clockwise order.

A triangulation of the polygon means decomposing its area into a set of non-overlapping triangles, where the sides of these triangles can be polygon sides or interior diagonals. Of course, in this task, every diagonal used in the triangulation is also colored with one of the three colors.

Such a triangulation is called “very good” if, for each of the $n - 2$ triangles, all three of its sides have different colors.

Your task is to determine whether the given polygon with its diagonals is correctly triangulated, and whether that triangulation is very good.

Input Format

The input has $n$ lines.

The first line contains a positive integer $T$, which indicates the Subtask number for this test.

The second line contains a positive integer $n$, as described in the Description section.

The third line contains a positive integer with $n$ digits. These digits represent the colors of the polygon sides. More precisely, the first digit represents the color of side $(1, 2)$, the second digit represents the color of side $(2, 3)$, the $i$-th digit represents the color of side $(i, i+1)$, and in particular, the $n$-th digit represents the color of side $(n, 1)$. Colors are denoted by digits $1, 2, 3$.

The next $n - 3$ lines each contain a description of a diagonal in the format x y c, where $x$ and $y$ are polygon vertices, and $c$ is the color of the diagonal. The input guarantees that vertices $x$ and $y$ are neither equal nor adjacent.

Output Format

Output one line.

• If the input polygon is not correctly triangulated, output $\mathtt{neispravna \space triangulacija}$.
• If the input polygon has a correct triangulation, but the triangulation is not good, output $\mathtt{neispravno \space bojenje}$.
• Otherwise, output $\mathtt{tocno}$.

1
5
12113
1 3 3
2 5 2

neispravna triangulacija

1
4
1212
1 3 2

neispravno bojenje

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

tocno

Hint

Constraints and Notes

This problem uses bundled tests.

In particular, for $100\%$ of the testdata, $1 \le T \le 5$.

Notes

The scoring of this problem follows the original COCI problem setting, with a total of $110$ points.

Translated from COCI2019-2020 CONTEST #2 T3 Checker.

Translated by ChatGPT 5