This problem involves verifying whether a given set of diagonals forms a valid triangulation of a convex polygon and, if so, whether the coloring of edges satisfies the "very good" condition.

Key Observations

• The first input value T denotes the subtask number, not the number of test cases.
• All polygon edges (including boundary edges) must be considered during validation.
• Each diagonal should be stored with the smaller vertex index as the source to maintain consistency.

Validation Strategy

A valid triangulation of an n-gon must contain exactly n−3 non-crossing diagonals that partition the polygon in to n−2 triangles. We validate this using the following approach:

1. For each vertex i, collect all incident edges (both polygon sides and diagonals).
2. Sort these edges by their adjacent vertex indices.
3. For every pair of consecutive edges in this sorted list (say, to vertices u and v), check if the edge (u, v) exists. If not, the triangulation is invalid.

This works because in any valid triangulation, the region around each vertex is divided into triangles, so consecutive neighbors must be connected.

Color Validation

A triangulation is "very good" if, in every triangle, all three edges have distinct colors. This is equivalent to checking that for every vertex, no two consecutive incident edges (in angular order) share the same color—because those two edges plus their connecting edge form a triangle.

Implementation Details

• Store edges in adjacency lists per vertex, with destination and color.
• Include original polygon edges: edge from i to i+1 (or n to 1) with color derived from input string.
• Sort adjacency lists by neighber index to simulate angular order.
• Use binary search to efficiently check existence of the closing edge between two neighbors.

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200010;

struct Edge {
    int to, color;
    bool operator<(const Edge& other) const {
        return to < other.to;
    }
};

vector<Edge> adj[MAXN];
char colorStr[MAXN];
int n;

inline int readInt() {
    int x = 0;
    char c = getchar();
    while (!isdigit(c)) c = getchar();
    while (isdigit(c)) {
        x = x * 10 + (c - '0');
        c = getchar();
    }
    return x;
}

int findEdgeColor(int u, int v) {
    auto it = lower_bound(adj[u].begin(), adj[u].end(), Edge{v, 0});
    if (it != adj[u].end() && it->to == v) {
        return it->color;
    }
    return 0;
}

int main() {
    readInt(); // subtask id, ignored
    n = readInt();
    scanf("%s", colorStr + 1);

    // Add polygon boundary edges
    for (int i = 1; i <= n; ++i) {
        int next = (i == n) ? 1 : i + 1;
        adj[i].push_back({next, colorStr[i] - '0'});
    }

    // Read diagonals
    for (int i = 0; i < n - 3; ++i) {
        int a = readInt(), b = readInt(), col = readInt();
        if (a > b) swap(a, b);
        adj[a].push_back({b, col});
    }

    // Sort adjacency lists
    for (int i = 1; i <= n; ++i) {
        sort(adj[i].begin(), adj[i].end());
    }

    bool validTriangulation = true;
    bool properColoring = true;

    for (int u = 1; u <= n; ++u) {
        const auto& edges = adj[u];
        for (size_t i = 1; i < edges.size(); ++i) {
            int v1 = edges[i - 1].to;
            int v2 = edges[i].to;
            int closingColor = findEdgeColor(v1, v2);
            if (closingColor == 0) {
                validTriangulation = false;
                break;
            }
            int c1 = edges[i - 1].color;
            int c2 = edges[i].color;
            if (c1 == c2 || c1 == closingColor || c2 == closingColor) {
                properColoring = false;
            }
        }
        if (!validTriangulation) break;
    }

    if (!validTriangulation) {
        puts("neispravna triangulacija");
    } else if (properColoring) {
        puts("tocno");
    } else {
        puts("neispravno bojenje");
    }

    return 0;
}