扩展域并查集解决了有多种相互关系的问题。这题如果单纯的去判断是不是同类就是用普通的并查集就可以了。但由于有想吃的关系，所以得使用扩展域并查集，有三种动物，将并查集的数组扩大三倍。对于某x,y两个动物是同类的情况这两个动物可能是A,B,C任意一种。那么将x,y合并。x+n,y+n合并。y+2*n,x+2*n合并。来代表他们是同一种动物。如果x吃y的话，那么假设x为A，y+n是B。所以将x和y+n合并表示x吃y的关系。同样如果x是B或C也要进行合并。
这样我们要进行判断的时候，一个是判断数据是否合理，
如果D==1的话判断x,y有没有之前已经记录的吃的关系。
如果D==2的话判断x,y有没有记录过得同类的关系以及有没有y吃x的关系。 
#include <bits/stdc++.h>

// #define int long long

using namespace std;
const int maxn = 200000;
int a[maxn];

int find(int x) {
    if (a[x]==x) {
        return x;
    } else {
        return a[x] = find(a[x]);
    }
}

void Merge(int x, int y) {
    int rootx = find(x);
    int rooty = find(y);
    a[rootx] = rooty;
}

signed main() {
    //
    for (int i=0;i<maxn;i++) {
        a[i] = i;
    }
    int n, k;
    int ans =0 ;
    int d, x, y;
    cin>>n>>k;
    for (int i=0;i<k;i++) {
        cin>>d>>x>>y;
        if (d==1) {
            if (x>n||y>n||find(x+n)==find(y)||find(y+n)==find(x)) {
                ans++;
            } else {
                Merge(x, y);
                Merge(x+n, y+n);
                Merge(x+2*n, y+2*n);
            }
        } else {
            if (x>n||y>n||x==y||find(x)==find(y)||find(y)==find(x+n)) {
                ans++;
            } else {
                Merge(x, y+n);
                Merge(x+n, y+2*n);
                Merge(x+2*n, y);
            }
        }
    }
    cout<<ans<<endl;
    
    return 0;
}