Description

In a certain city, there are n residents. Any two people who know each other are either friends or enemies, and the following conditions are satisfied:

1. A friend of my friend is my friend.
2. An enemy of my enemy is my friend.
   All people who are friends form a gang.

Given m pieces of information about these n people—indicating whether two people are friends or enemies—write a program to calculate the maximum possible number of gangs in the city.

Input Format

The first line contains n and m, where 1 < n ≤ 1000 and m ≤ 5000.
Each of the following m lines contains p x y, where p is either 0 or 1. If p is 0, it means x and y are friends; if p is 1, it means x and y are enemies.

Output Format

An integer representing the maximum possible number of gangs among these n people.

6 4
1 1 4
0 3 5
0 4 6
1 1 2

3