5622: ABC177——D - Friends
[Creator : ]
Description
There are $N$ persons called Person $1$ through Person $N$.
You are given $M$ facts that "Person $A_i$ and Person $B_i$ are friends." The same fact may be given multiple times.
If $X$ and $Y$ are friends, and $Y$ and $Z$ are friends, then $X$ and $Z$ are also friends. There is no friendship that cannot be derived from the $M$ given facts.
Takahashi the evil wants to divide the $N$ persons into some number of groups so that every person has no friend in his/her group.
At least how many groups does he need to make?
If $X$ and $Y$ are friends, and $Y$ and $Z$ are friends, then $X$ and $Z$ are also friends. There is no friendship that cannot be derived from the $M$ given facts.
Takahashi the evil wants to divide the $N$ persons into some number of groups so that every person has no friend in his/her group.
At least how many groups does he need to make?
Input
First line contains two integers $N\ (2 \leq N \leq 2 \times 10^5),\ M\ (0 \leq M \leq 2 \times 10^5)$.
The following $M$ lines, each line contains two integer. The $i$-th line is $A_i\ B_i\ (1 \leq A_i,\ B_i \leq N,\ A_i \neq B_i)$.
The following $M$ lines, each line contains two integer. The $i$-th line is $A_i\ B_i\ (1 \leq A_i,\ B_i \leq N,\ A_i \neq B_i)$.
Output
Print the answer.
Sample 1 Input
5 3
1 2
3 4
5 1
Sample 1 Output
3
Dividing them into three groups such as $\{1,\ 3\},\ \{2,\ 4\}$, and $\{5\}$ achieves the goal.
Sample 2 Input
4 10
1 2
2 1
1 2
2 1
1 2
1 3
1 4
2 3
2 4
3 4
Sample 2 Output
4
Sample 3 Input
10 4
3 1
4 1
5 9
2 6
Sample 3 Output
3
HINT
题目来源:AtCoder ABC 177 D 题。