En un reino animal existen tres tipos de criaturas: A, B y C, cuyas relaciones de depredación forman un ciclo: A se alimenta de B, B de C y C de A. Se nos presanta un conjunto de N animales, identificados del 1 al N. Cada animal pertenece a una de estas tres categorías, pero su tipo específico es desconocido inicialmente.

Se nos proporcionan K declaraciones sobre las relaciones entre estos animales. Cada declaración es de uno de dos tipos:

• Tipo 1: "X e Y son del mismo tipo."
• Tipo 2: "X se alimenta de Y."

Algunas de estas declaraciones pueden ser falsas. Una declaración se considera falsa si cumple alguna de las siguientes condiciones:

1. Entra en conflicto con una o más declaraciones verdaderas previamente establecidas.
2. La declaración involucra a un animal con un número mayor que N.
3. La declaración afirma que un animal se alimenta de sí mismo (X come a X).

El objetivo es calcular el número total de declaraciones falsas dadas las N criaturas y las K declaraciones.

Entrada

La primera línea contiene dos enteros, N y K, separados por un espacio. Las siguientes K líneas describen las declaraciones, cada una con tres enteros: D, X e Y, separados por espacios. D indica el tipo de declaración: 1 si X e Y son del mismo tipo, y 2 si X se alimenta de Y.

Salida

Se debe imprimir un único entero que represente el número total de declaraciones falsas.

Ejemplo de Entrada

100 7
1 101 1 
2 1 2
2 2 3 
2 3 3 
1 1 3 
2 3 1 
1 5 5

Ejemplo de Salida

3

Solución Utilizando Union-Find

Este problema puede resolverse eficientemente utilizando una estructura de datos Union-Find (Conjuntos Disjuntos) modificada. La clave está en expandir la estructura para manejar las tres posibles relaciones (ser del mismo tipo, ser el tipo que se alimenta, ser el tipo que es alimentado) para cada animal.

Para cada animal i (de 1 a N), podemos representar sus tres posibles estados (ser tipo A, ser tipo B, ser tipo C) utilizando tres nodos en nuestro grafo de Union-Find: i, i + N, y i + 2N. Aquí, i puede representar el estado "es tipo A", i + N el estado "es tipo B", y i + 2N el estado "es tipo C".

Representación de Relaciones:

• Si X e Y son del mismo tipo (D=1):
  • Unimos X con Y (ambos son tipo A).
  • Unimos X + N con Y + N (ambos son tipo B).
  • Unimos X + 2N con Y + 2N (ambos son tipo C).
• Si X se alimenta de Y (D=2):
  • Unimos X con Y + N (si X es A, Y es B).
  • Unimos X + N con Y + 2N (si X es B, Y es C).
  • Unimos X + 2N con Y (si X es C, Y es A).

Detección de Falsedad:

Se incrementa el contador de falsedades si:

• Para D=1: Si X y Y ya pertenecen al mismo conjunto que indica una relación de depredación (ej. X está en el mismo conjunto que Y + N o Y + 2N), la declaración es falsa.
• Para D=2: Si X y Y ya pertenecen al mismo conjunot indicando que son del mismo tipo (ej. X está en el mismo conjunto que Y), o si la declaración implica un ciclo incorrecto (ej. X está en el mismo conjunto que Y + 2N), la declaración es falsa.
• Además, se debe verificar si X o Y son mayores que N o menores que 1. Si es así, la declaración es falsa.

La función find(i) devuelve la raíz del conjunto al que pertenece el elemento i. La función unite(i, j) fusiona los conjuntos que contienen i y j. La función same(i, j) verifica si i y j pertenecen al mismo conjunto.

#include <vector>
#include <numeric>

class UnionFind {
private:
    std::vector<int> parent;
    std::vector<int> rank;

public:
    UnionFind(int size) {
        parent.resize(size);
        std::iota(parent.begin(), parent.end(), 0); // Inicializa cada elemento como su propio padre
        rank.assign(size, 0); // Inicializa rangos a 0
    }

    int find(int i) {
        if (parent[i] == i) {
            return i;
        }
        return parent[i] = find(parent[i]); // Path compression
    }

    void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            if (rank[root_i] < rank[root_j]) {
                parent[root_i] = root_j;
            } else if (rank[root_i] > rank[root_j]) {
                parent[root_j] = root_i;
            } else {
                parent[root_j] = root_i;
                rank[root_i]++;
            }
        }
    }

    bool are_connected(int i, int j) {
        return find(i) == find(j);
    }
};

int main() {
    int n, k;
    scanf("%d %d", &n, &k);

    UnionFind uf(n * 3); // 3 * N elementos para representar los 3 tipos de cada animal
    int false_declarations = 0;

    for (int i = 0; i < k; ++i) {
        int type, x, y;
        scanf("%d %d %d", &type, &x, &y);
        
        // Ajustar índices a base 0 y verificar límites
        --x; --y;
        if (x < 0 || x >= n || y < 0 || y >= n) {
            false_declarations++;
            continue;
        }

        int x_type_a = x;
        int x_type_b = x + n;
        int x_type_c = x + 2 * n;

        int y_type_a = y;
        int y_type_b = y + n;
        int y_type_c = y + 2 * n;

        if (type == 1) { // X e Y son del mismo tipo
            // Si X es A, Y no puede ser B o C. Si X es B, Y no puede ser A o C. Si X es C, Y no puede ser A o B.
            if (uf.are_connected(x_type_a, y_type_b) || uf.are_connected(x_type_a, y_type_c)) {
                false_declarations++;
            } else {
                uf.unite(x_type_a, y_type_a);
                uf.unite(x_type_b, y_type_b);
                uf.unite(x_type_c, y_type_c);
            }
        } else { // X se alimenta de Y (Type 2)
            // Si X come a Y, X no puede ser del mismo tipo que Y, ni X puede ser C si Y es A.
            if (uf.are_connected(x_type_a, y_type_a) || uf.are_connected(x_type_c, y_type_a)) {
                false_declarations++;
            } else {
                uf.unite(x_type_a, y_type_b); // Si X es A, Y es B
                uf.unite(x_type_b, y_type_c); // Si X es B, Y es C
                uf.unite(x_type_c, y_type_a); // Si X es C, Y es A
            }
        }
    }

    printf("%d\n", false_declarations);

    return 0;
}