레이팅 미적용Aliens are visiting Earth and, as usual, they plan to abduct humans for their experiments. In the past, alien abductions have caused a lot of press coverage and wild speculation on Earth. Luckily for them, most people do not believe these stories and think that aliens are not real.
In order to keep a low profile in the future, the Galactic Committee for Person Captures (GCPC) has established rules for abductions. Besides a lot of boring paperwork, the aliens have to prepare the abduction carefully. While they can make multiple trips (in fact, alien travel is so fast in practice that this is not a limitation at all), they must be smart about it so that their secret is not revealed to humans. If aliens want to abduct a person, they are required to abduct all of their friends at the same time, so that no one notices that their friend is missing when they want to hang out. Of course, friendships on planet Earth are bidirectional, that is if Alice is a friend of Bob, then Bob is also a friend of Alice.
In preparation for the trip, the aliens have observed their targets and started taking note of all their friendships. In total, they must abduct \(n\) people, including their friends. Now, they want to book a starship at their local dealership and wonder how much space they need to abduct all \(n\) people. A starship's storage space is measured in terms of the number of people that can be transported simultaneously. What is the minimum storage space required to abduct all \(n\) people?
The input consists of:
- One line with 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 total number of friendships between them.
- \(m\) lines, each with two integers \(i\) and \(j\) (\(1\leq i < j\leq n\)), denoting a friendship between persons \(i\) and \(j\).
The people are numbered from \(1\) to \(n\). It is guaranteed that no friendship is listed multiple times.
Output the minimum storage space needed to abduct all people.
5 3
1 2
2 3
4 5
3
3 0
1
8 8
1 2
2 3
3 4
1 4
1 5
2 6
3 7
4 8
8