import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int k = scanner.nextInt();
		int d, x, y;
		int result = 0;
		Food1182[] foods = new Food1182[n+1];
		for(int i=0; i<n+1; i++) {
			foods[i] = new Food1182(); 
		}
		Food1182 xAncester, yAncester;
		Food1182 ancester, enemy, food;
		for(int i=0; i<k; i++) {
			d = scanner.nextInt();
			x = scanner.nextInt();
			y = scanner.nextInt();
			if(x>n || y>n || (d==2 && x==y)) {
				result++;
//				System.out.println((i+1) + "\t" + d + "\t" + x + "\t" + y);
				continue;
			}
			xAncester = foods[x].getAncester();
			yAncester = foods[y].getAncester();
			if(d == 1) {	// same ancester
				if(xAncester == yAncester) {
					;
				} else if(xAncester.enemy == yAncester || xAncester.food == yAncester) {
					result++;
//					System.out.println((i+1) + "\t" + d + "\t" + x + "\t" + y);
				} else {	// 不同生态圈，合并
					ancester = combine(xAncester, yAncester);
					enemy = combine(xAncester.enemy, yAncester.enemy);
					food = combine(xAncester.food, yAncester.food);
					chain(ancester, enemy, food);
				}
			} else {	// eat
				if(xAncester.food == yAncester) {
					;
				} else if(xAncester.enemy == yAncester || xAncester == yAncester) {
					result++;
//					System.out.println((i+1) + "\t" + d + "\t" + x + "\t" + y);
				} else {
					ancester = combine(xAncester, yAncester.enemy);
					enemy = combine(xAncester.enemy, yAncester.food);
					food = combine(xAncester.food, yAncester);
					chain(ancester, enemy, food);
				}
			}
//			draw(i+1, foods, n);
		}
		System.out.println(result);
		scanner.close();
	}
	
	public static void chain(Food1182 ancester, Food1182 enemy, Food1182 food) {
		ancester.enemy = enemy;
		ancester.food = food;
		if(enemy != null) {
			enemy.enemy = food;
			enemy.food = ancester;
		}
		if(food != null) {
			food.enemy = ancester;
			food.food = enemy;
		}
	}
	
	public static Food1182 combine(Food1182 food1, Food1182 food2) {
		if(food1 == null) {
			return food2;
		}
		if(food2 == null) {
			return food1;
		}
		if(food1.weight < food2.weight) {
			food1.ancester = food2;
			food2.weight += food1.weight;
			return food2;
		} else {
			food2.ancester = food1;
			food1.weight += food2.weight;
			return food1;
		}
	}
}

class Food1182 {
	public int weight;
	public Food1182 ancester;
	public Food1182 enemy;
	public Food1182 food;
	
	public Food1182() {
		ancester = this;
		enemy = null;		
		food = null;
	}
	
	public Food1182 getAncester() {
		Food1182 ancester = this;
		while(ancester != ancester.ancester) {
			ancester.ancester = ancester.ancester.ancester;
			ancester = ancester.ancester;
		}
		return ancester;
	}
}

• Re:奇怪了，为什么老是超时？高手帮看看！带权，用了路径压缩，还是超时 (3065) tredcx 2018-07-15 20:12:04