技巧
    带权并查集
思路
    通过权重来类比元素之间的关系
    路径压缩的地方做文章
    如果之前两个元素在一个集合中，就通过两个权值判断相互关系验证真假
    如果没有关系怎么说都是真的 需要建立关系
实现 
package main

import (
	"bufio"
	. "fmt"
	"io"
	"os"
)

// 带权并查集节点
type Animal struct {
	id     int
	weight int
	father *Animal
}

// 压缩路径（更新权值）
func getRoot(x *Animal) *Animal {
	if x.father == nil {
		return x
	}
	father := x.father
	root := getRoot(x.father)
	x.weight = (x.weight + father.weight) % 3
	x.father = root
	return root
}

func same(x, y *Animal) bool {
	return getRoot(x) == getRoot(y)
}

// https://ac.nowcoder.com/acm/problem/16884
func NC16884(_r io.Reader, _w io.Writer) {
	in, out := bufio.NewReader(_r), bufio.NewWriter(_w)
	defer out.Flush()
	var N, K int
	Fscan(in, &N, &K)
	// 构建并查集
	set := make(map[int]*Animal)
	for i := 1; i <= N; i++ {
		set[i] = &Animal{i, 0, nil}
	}
	var fakeCnt int
	for i := 0; i < K; i++ {
		var D, X, Y int
		Fscan(in, &D, &X, &Y)
		// 当前的话中X或Y比N大，就是假话； 当前的话表示X吃X，就是假话。
		if X > N || Y > N || (D == 2 && X == Y) {
			fakeCnt++
		} else if same(set[X], set[Y]) { // 验证合理性
			xw, yw := set[X].weight, set[Y].weight
			if D == 1 && set[X].weight == set[Y].weight {
				continue
			} else if D == 2 && ((xw == 0 && yw == 1) || (xw == 1 && yw == 2) || (xw == 2 && yw == 0)) {
				continue
			}
			fakeCnt++
		} else { // 建立关联
			xr, yr := getRoot(set[X]), getRoot(set[Y])
			yr.father = xr
			yr.weight = (3 + set[X].weight + (D - 1) - set[Y].weight) % 3
		}
	}
	Fprintln(out, fakeCnt)
}

func main() {
	NC16884(os.Stdin, os.Stdout)
}