#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <math.h>
#include <bitset>
#include <vector>
#include <string>
#include <cstdio>
#include <cctype>
#include <numeric>
#include <fstream>
#include <sstream>
#include <cstdlib>
#include <iomanip>
#include <cassert>
#include <cstring>
#include <stdio.h>
#include <string.h>
#include <iterator>
#include <iostream>
#include <algorithm>
#include <strings.h>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#define fore(i, a, b) for (int i = (a), i##_last = (b); i < i##_last; ++i)
#define fort(i, a, b) for (int i = (a), i##_last = (b); i <= i##_last; ++i)
#define ford(i, a, b) for (int i = (a), i##_last = (b); i >= i##_last; --i)
#define fi first
#define se second
#define pb push_back
#define double long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;};
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
constexpr int MAX_N = 2E5 + 5;
int N, T;
string c;
vector<int> g[MAX_N];
map<pair<int, int>, int> f;
bool isInOrder(const int l, const int m, const int r) {
if (l < r)
return l <= m && m <= r;
if (l > r)
return l <= m || m <= r;
return l == m;
}
int getNext(const int x) {
return x == N ? 1 : (x + 1);
}
int getPrevious(const int x) {
return x == 1 ? N : (x - 1);
}
void addSide(const int x, const int y, const int c) {
g[x].push_back(y);
g[y].push_back(x);
f[make_pair(x, y)] = f[make_pair(y, x)] = c;
}
bool checkTriangulation() {
/**
Choose any diagonal and split the polygon
then there should be no diagonal from one of two new polygons
that go outside
Implementation
Iterate from 1 to N
and consider sides
if the index of vertex is smaller than the current one then
it is one of the edges considered earlier and
there is no need to consider it in this and later iterations
therefore we can ignore it
otherwise
it is one of new boundary (the diagonal along which we have to cut)
that we must consider
To store the currently considered boundaries, we can use stack (last-in first-out)
as the boundaries we start considering later should be removed/ignored earlier
**/
if (f.size() != 4 * N - 6)
return false;
stack<int> p;
fort(x, 1, N) {
ford(i, sz(g[x]) - 1, 0) {
const int &y = g[x][i];
if (y < x) {
p.pop();
continue;
}
if (!p.empty() && p.top() < y)
return false;
p.push(y);
}
}
return true;
}
bool checkPatriotic() {
/**
Sort the adjacent vertices
and check the color
**/
fort(x, 1, N)
fore(i, 1, sz(g[x])) {
const int &y = g[x][i],
&z = g[x][i - 1],
&a = f[make_pair(x, y)],
&b = f[make_pair(x, z)],
&c = f[make_pair(y, z)];
if (a == b || b == c || a == c)
return false;
}
return true;
}
signed main() {
#ifdef LOCAL
freopen("input.INP", "r", stdin);
#endif // LOCAL
cin.tie(0) -> sync_with_stdio(0);
cout.tie(0);
cin >> T >> N >> c;
fort(x, 1, N)
addSide(x, getNext(x), c[x - 1] - '0');
for (int e = N - 3, X, Y, C; e > 0; --e) {
cin >> X >> Y >> C;
addSide(X, Y, C);
}
fort(x, 1, N)
sort(all(g[x]), [&](const int &l, const int &r) -> bool {
const bool u = (x < l), v = (x < r);
if (u != v)
return u;
return l < r;
});
if (!checkTriangulation()) {
puts("neispravna triangulacija");
return 0;
}
if (!checkPatriotic()) {
puts("neispravno bojenje");
return 0;
}
puts("tocno");
return 0;
}
