标题

动物王国中有三类动物A,B,C，这三类动物的食物链构成了风趣的环形。

A吃B，B吃C，C 吃A

现有N个动物，以1∼N编号。

每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。

有人用两种说法对这N个动物所构成的食物链关系进行描述：

榜首种说法是1 X Y，表明X和Y是同类。

第二种说法是2 X Y，表明X吃Y

此人对N 个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。

当一句话满意下列三条之一时，这句话便是假话，否则便是真话。

1. 当时的话与前面的某些真的话冲突，便是假话；
2. 当时的话中X或Y比N大，便是假话；
3. 当时的话表明X吃X，便是假话。

你的任务是根据给定的N和K句话，输出假话的总数。

输入格局

榜首行是两个整数N和K，以一个空格分隔。

以下K行每行是三个正整数D，X，Y两数之间用一个空格隔开，其间D 表明说法的品种。

若D=1，则表明X 和Y是同类。

若D=2，则表明X吃Y

输出格局

只有一个整数，表明假话的数目。

数据规模

1≤N≤50000
0≤K≤100000

输入样例：

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

输出样例：

3

代码

import java.util.Scanner;
public class Main {
    static int n, k, N = 50010;
    static int[] p = new int[N], dis = new int[N];
    // 并查集查找函数，查找元素x地点调集的根节点，并更新dis数组
    public static int find(int x) {
        if (p[x] != x) {
            // 递归查找x的根节点，并更新x到根节点的距离
            int t = find(p[x]);
            dis[x] += dis[p[x]];
            p[x] = t; // 途径紧缩，将x的父节点直接指向根节点
        }
        return p[x];
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt(); // 人数
        k = in.nextInt(); // 业务数
        // 初始化并查集和距离数组
        for (int i = 1; i <= n; i++) {
            p[i] = i; // 初始化每个人的父节点为自己
        }
        int ans = 0; // 记载不能确认的业务数量
        while (k > 0) {
            k--;
            int d = in.nextInt(); // 业务类型
            int a = in.nextInt(); // 人a
            int b = in.nextInt(); // 人b
            // 若a或b超出人数规模，则该业务无效，直接跳过
            if (a > n || b > n) {
                ans++;
            } else {
                int pa = find(a); // 人a地点调集的根节点
                int pb = find(b); // 人b地点调集的根节点
                if (d == 1) { // 业务类型为1，表明a和b是同类关系
                    if (pa == pb && (dis[a] - dis[b]) % 3 != 0) ans++;
                    else if (pa != pb) { // 若a和b不在同一个调集中，则兼并调集
                        p[pa] = pb; // 将a地点调集的根节点指向b地点调集的根节点
                        dis[pa] = dis[b] - dis[a]; // 更新a地点调集中元素到根节点的距离
                    }
                } else { // 业务类型为2，表明a是b的上级
                    if (pa == pb && (dis[a] - dis[b] - 1) % 3 != 0) ans++;
                    else if (pa != pb) { // 若a和b不在同一个调集中，则兼并调集
                        p[pa] = pb; // 将a地点调集的根节点指向b地点调集的根节点
                        dis[pa] = dis[b] - dis[a] + 1; // 更新a地点调集中元素到根节点的距离
                    }
                }
            }
        }
        System.out.println(ans); // 输出不能确认的业务数量
    }
}