1182.cpp

#include <iostream>
#include <vector>
#include <list>
#include <map>
//#include <unordered_map>
#include <queue>
#include <algorithm>
#include <string>
#include <memory>  
#include <cstring>
using namespace std;

#include <stdio.h>
#include <stdlib.h>


struct Shit {
    int p; //parent
    int r; //0 - same as p, 1 - eats p, 2 - eaten by p
};

const int MAXN = 50000;

Shit shits[MAXN + 1];

int findset(int x) {
    if (shits[x].p != x) {
        int parent = shits[x].p;
        int root = findset(parent);
        shits[x].p = root;
        shits[x].r = (shits[x].r + shits[parent].r) % 3;
    }
    return shits[x].p;
}

int unionset(int x, int y, int r) {
    int rx = findset(x);
    int ry = findset(y);
    shits[rx].p = ry;
    // x.r + rx.r <=> r + y.r
    shits[rx].r = (r + shits[y].r - shits[x].r + 3) % 3;
    return ry;
}

int main() { 
  for (int i = 0; i <= MAXN; ++i) {
    shits[i].p = i;
    shits[i].r = 0;
  }
  int count = 0;
  int n, k;
  scanf("%d%d", &n, &k);
  for (int i = 0; i < k; ++i) {
    int d, x, y;
    scanf("%d%d%d", &d, &x, &y);
    if (x > n || y > n || d == 2 && x == y) {
        count++;
    } else {
        int rx = findset(x);
        int ry = findset(y);
        if (rx == ry) {
          int xyr = (shits[x].r - shits[y].r + 3) % 3;
          if (xyr != d - 1) count++;
        } else {
          unionset(x, y, d - 1);
        }
    }
  }
  cout << count << endl;
  return 0;
}