All Tracks Algorithms Graphs Strongly Connected Components Problem

Magical Islands
Tag(s):

Easy-Medium

Problem
Editorial
Analytics

Tecnoesis'16 is going on in NIT Silchar. Under the fun module there is one event Magical Islands. In this game you'll be given one real life map and the map is represented by N nodes and M edges. There're are some directed simple path that connects node u to node v. Maps contains some nodes which are magical, means if you start from those nodes and each time if you choose only one edge connected from it then you can visit at most X nodes(including the start node). Also if you keep moving infinite amount of time you may visit same X nodes multiple no of times.

So, always you would like to visit maximum no of nodes. So, you have to choose a start node such that X is maximum. Find the value of maximum X possible in given map.

Input

First line contains two integers N and M, no of nodes and no of edges. Next M lines contains two integers u and v. There is a directed edge from u to v.

Output

Print single integer X.

Constraints

1 ≤ N ≤ 100000, 1 ≤ M ≤ 200000 1 ≤ u, v ≤ N

Problem Setter : Sourav Kumar Paul

SAMPLE INPUT
5 6
1 2
2 3
3 1
4 2
3 4
3 5
SAMPLE OUTPUT
4
Explanation

If you choose any node except node 5 you can visit at most 4 nodes which is maximum.

Suppose you start from node 1. 1 -> 2 -> 3 -> 4 -> 2 -> ....

Time Limit: 5.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Notifications
View All Notifications