The Gang

Problem Background

Special for beginners, ^_^

Problem Description

In a certain city there live $n$ people. Any two acquaintances are either friends or enemies, and they satisfy:

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 — that two particular people are friends, or that two particular people are enemies — please write a program to compute the maximum possible number of gangs in this city.

Input Format

The first line contains $n$ and $m$, with $1 < n < 1000$, $1 \le m \le 10^5$.

The following $m$ lines each contain $p\ x\ y$. $p$ is $0$ or $1$. When $p = 0$, it means $x$ and $y$ are friends; when $p = 1$, it means $x$ and $y$ are enemies.

Output Format

One integer: the maximum possible number of gangs among these $n$ people.

Sample Input

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

Sample Output

3

Constraints

Time limit: 1s; memory limit: 1024 KiB for each test case.