The princess of PonyLand would like to play with her friends
(she has lots of friends), but she is a peace loving
creature so she does not want to invite ponies who hate
each other (those usually end up quarrelling).
Fortunately recent advances in online social networking in PonyLand produced a hugely successful anti-social website that collects data about which ponies hate each other. Of course the princess cannot simply access to this data due to proper privacy regulations in PonyLand, but she is in negotiations with the anti-social website owners. While the negotiation is going on, an anonymized version of the anti-social graph of her friends is available. Preparing for the party, the princess would like at least to know how many ponies she can invite at most. |
![]() photo by FreydĂs source: http://www.flickr.com/photos/22329928@N08/4434576086 |
The input is the anonymized anti-social graph. First line contains N and M the number of vertices and edges, the following M lines contain two numbers between 0 and N-1, an edge of the graph.
It turns out that the anti-social graph in PonyLand has no cycles in it.
4 3 0 1 0 2 0 3
3