import java.io.*;
import java.util.*;

public class Main {

    private static int N = 50010;
    private static int[] p = new int[N];
    private static int[] distance = new int[N];

    private static int find(int x) {
        if (p[x] != x) {
            int root = find(p[x]);
            distance[x] += distance[p[x]];
            p[x] = root;
        }
        return p[x];
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        for (int i = 1; i <= n; i++) {
            p[i] = i;
        }
        int res = 0;

        for (int i = 0; i < m; i++) {
            int op = sc.nextInt();
            int x = sc.nextInt();
            int y = sc.nextInt();
            if (x > n || y > n) {
                res++;
                continue;
            }
            int px = find(x);
            int py = find(y);
            // same group
            if (op == 1) {
                if (px == py && (distance[x] - distance[y]) % 3 != 0) {
                    res++;
                } else if (px != py) {
                    p[px] = py;
                    distance[px] = distance[y] - distance[x];
                }
            } else {
                if (px == py && (distance[x] - distance[y] - 1) % 3 != 0) {
                    res++;
                } else if (px != py) {
                    p[px] = py;
                    distance[px] = distance[y] + 1 - distance[x];
                }
            }
        }
        System.out.println(res);
    }
}

谈一下自己的一点理解。代码来自Y总的讲解。

一开想到的是维护x y z 三个集合。这样可以很容易判断出每个元素和集合的关系。但是发现这样是错的，因为对于一个新的a，b，如果之前没有在集合当中，没有办法判断他们和现有集合的关系，a吃b，a应该在x y z哪个当中没有办法确定。

所以这道题最巧妙也是最迷惑性的地方在于，并查集本质上维护的是已经处理过的为真的声明的集合。对于每个新的声明，判断和之前处理过的声明的关系，如果为真，就和当前的集合进行合并。产生矛盾就是假声明，这也就是为什么我们只在px==py的时候才会res++。
举个极端一点的例子，10个数，前5句声明分别涉及(a1,a2), (a3, a4) … (a9, a10) 因为这五句声明涉及了10个不同的数，互相不会产生矛盾，所以会形成 5 个小集合。那么第六句声明，(ai, aj) 就可以通过这这五个小集合（已经处理过的为真的声明的集合）来判断是否有矛盾。

一些细节：
1. 距离负数问题，同余对于负数也是同样适用的。i.e. -9 % 5 = 1 可以理解为负数加上n个k，使之变为正数，在求余数。a % k == (a + n * k) % k .
2. 关于后边判断 if（px == py && (d[x] - d[y]) %3 == 0)) 为什么要判断px == py。一开始每个集合只有一个元素，父节点就是自己。如果px == py，在这道题的含义并不是说x 和 y是同类。而是说，这在之前这两个节点被提及过。如果被提及过，就会合并为一个集合。因为我们用到根节点的距离来判断节点的关系。所以后边才会做同余判断。如果不同余，说明之前的话是真话，但是这一句话和之前的矛盾，那么就是假话。
3. 如果px != py 说明这两个节点之前没有提过，就肯定不会产生矛盾。就一定是真话，所以要合并为一个集合，对距离关系做处理。比如前边5句话都在说 节点 1-10， 第6句话说节点 98，99。那么这句话一定为真。
4. 距离数组中存储的数，并不是真的到根节点的距离，而是对3同余后的余数为，0，1，2的数。所以负数也可以。