This is a simple DSU question. The general idea is as follows:

In reality, we only need to seriously check the last of the third conditions, as the first 2 are trivial. We will assign each node a value from $$$0 - 2$$$ corresponding to the letters $$$A - C$$$ in the statement. For each query $$$t \; u \; v$$$, we first check whether the nodes are in the same component. If they are, we will simply check whether the given query is true or false with the following rules:

Type 1: $$$val[u] = val[v]$$$
Type 2: $$$(val[u] + 1) \bmod 3 = val[v]$$$

If they are not in the same component, we will have to merge them. For both components, we will already have the relative order of all elements in each component. Then the only thing we need to change is the relationship between $$$u$$$ and $$$v$$$. We check how much we need to change either $$$u$$$ or $$$v$$$ according to the rules above, and we will increment each node in one component by that value. How to choose which component to change? We will always choose the smaller one, since the small-to-large trick will guarantee $$$O(N\log N)$$$, which is our final time complexity.

I came up with a solution (got AC):

Imagine the N animals as a network of components. In the network let x eats y be represented by an arrow x -> y. Let d(x, y) be the number of arrows from x to y modulo 3. The distances are taken modulo 3 because in a scenario like this: a -> b -> c -> d, a and d are really the same type.

Maintain an array d where for each animal v, d[v] = d(v, p[v]), where p[v] is the parent of the animal (I did not use path compression). Thus if x and y are in the same component, i.e. find(x) == find(y), answering the query is straightforward, as we can compute d(x, y) = d(x, find(x)) - d(y, find(x)). Finding d(x, find(x)) is easy since we can just walk up the chain starting at x: d(x, find(x)) = d(x, p[x]) + d(p[x], p[p[x]]) + ... + d(p...p[x], find(x)), same for d(y, find(y)).

If x and y are not in the same component, you need to link find(x) to find(y) so that p[find(x)] = find(y) (or vice versa, use the union by size heuristic) and set the value of d(find(x), find(y)) in such a way that d(x, y) = type - 1. You can easily come up with a formula for what d(find(x), find(y)) should be.

The time complexity is $$$O(N + K\text{log}(N))$$$.

Edit: code:

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

using ll = long long;
using ld = long double;
#define sz(x) int((x).size())

int N, K;
vector<int> p;
vector<int> sz;

// d[i] := d(i, p[i]).
vector<int> d;

void build() {
    p.assign(N + 1, 0);
    iota(p.begin(), p.end(), 0);
    sz.assign(N + 1, 1);
    d.assign(N + 1, 0);
}

int find(int u) {
    while (u != p[u]) {
        u = p[u];
    }
    return u;
}

bool same(int u, int v) { return find(u) == find(v); }

// dist[u] := d(u, find(u)).
int dist(int u) {
    int ret = 0;
    while (u != p[u]) {
        ret += d[u];
        u = p[u];
    }
    return ret % 3;
}

// dist(u, v) := d(u, v).
int dist(int u, int v) { return (dist(u) - dist(v) + 3) % 3; }

void unite(int u, int v, int distance) {
    int ru = find(u);
    int rv = find(v);
    assert(ru != rv);
    if (sz[ru] > sz[rv]) {
        swap(u, v);
        swap(ru, rv);
        distance = (3 - distance) % 3;
    }
    // link ru to rv
    p[ru] = rv;
    d[ru] = (distance + dist(v) - dist(u) + 3) % 3;
    sz[rv] += sz[ru];
}

void solve() {
    cin >> N >> K;

    build();
    int cntFalse = 0;
    for (int i = 0; i < K; i++) {
        int type, x, y;
        cin >> type >> x >> y;
        if (x > N || y > N) {
            cntFalse++;
            continue;
        } else {
            type--;
            if (same(x, y)) {
                if (dist(x, y) != type) {
                    cntFalse++;
                }
            } else {
                unite(x, y, type);
            }
        }
    }

    cout << cntFalse << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.setf(ios::fixed);
    cout.precision(15);

    int t;
    cin >> t;
    for (int i = 1; i <= t; i++) {
        solve();
    }

    return EXIT_SUCCESS;
}