Codah Club연습하고, 제출하고, 성장하세요.
로그인
한국어
#000151

Tribe

Not many people know for Msongwa Tue, a tribe from eastern Mianmar. Their unique mimic was problem for a scientist called Meštar Frane.


While Meštar was exploring Mianmar, he discovered that some of its native inhabitants (yes, Msongwa Tuevians) consider handshake as an invitation to breed. Meštar tried to handshake one of them not knowing what he was doing. He's in big trouble now since some Msongwa Tuevians think that Meštar is a perv. He still needs some information about their culture though.


Msongwa Tuevians are also very social and talkative. If two of them know each other, they share every information they have.


Whoah! Meštar has just found a list of their friendship! Now he can find out how many Msongwa Tuvians won't talk to him (because they know about his "handshake) in the worst-case scenario.



InputThe first line of the standard input contains two numbers: N and M. N ( 0< N <= 50000 ) is the number of different Msongwa Tuevians, and M ( 0< M <= 50000 ) is the number of friendships. Following M lines contain 2 numbers each i andj ( 0 < i < j <= N ) that describe a friendship ( i-th Msongwa Tuevian is a friend of j-th ).


OutputTo the standard output write one number that is the maximum possible number of Msongwa Tuevians which heard about Meštar's mistake.



Input:
5 4
1 2
2 3
3 4
4 2
Output:
4

Explanation: In the worst-case scenario, Meštar encountered Msongwa Tuevian with ID from 1 to 4 - after gossiping all four won't talk to Meštar.

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.