Alien Attack 2

Interview

Time limit4sMemory limit1024 MB

Summary

Given a friendship graph, find the size of the largest connected group, since each person's friends must be abducted together.

Level: Easy3 of 10
Topics: Graph, Union-find, BFS
Solved: No attempts yet

Problem

Aliens are visiting Earth, and as usual, they plan to abduct humans for their experiments. In the past, alien abductions drew a lot of press coverage and wild speculation. Luckily for them, most people do not believe these stories and think aliens are not real.

To keep a low profile in the future, the Galactic Committee for Person Captures (GCPC) has set rules for abductions. The aliens must prepare each abduction carefully. They may make multiple trips (alien travel is so fast in practice that this is no real limitation), but they must be smart about it so that humans do not discover their secret. If aliens want to abduct a person, they must abduct all of that person's friends at the same time, so that no one notices a friend is missing when they try to hang out. Friendships on Earth are bidirectional: if Alice is a friend of Bob, then Bob is also a friend of Alice.

The aliens have observed their targets and recorded all their friendships. In total, they must abduct $n$ people, including their friends. They want to book a starship and need to know how much space it requires to abduct all $n$ people. A starship's storage space is measured by the number of people it can transport at the same time. What is the minimum storage space required to abduct all $n$ people?

Input

The first line contains two integers $n$ and $m$ ( $1 \leq n \leq 2 \cdot 10^5$ , $0 \leq m \leq 2 \cdot 10^5$ ), the number of people and the number of friendships. Each of the next $m$ lines contains two integers $i$ and $j$ ( $1 \leq i < j \leq n$ ), meaning persons $i$ and $j$ are friends. No friendship is listed more than once.

Output

Print the minimum storage space needed to abduct all people.

Examples3

Example 1
Input
```
5 3
1 2
2 3
4 5
```
Expected output
```
3
```
Example 2
Input
```
3 0
```
Expected output
```
1
```
Example 3
Input
```
8 8
1 2
2 3
3 4
1 4
1 5
2 6
3 7
4 8
```
Expected output
```
8
```