Anya, as a future world champion in programming, commissioned a very responsible job. The Government of the \textbf{N}-region presents her plan for building roads between cities. Under the plan, all the roads one-way, but between the two cities may be more than one way, perhaps in different directions. Anya is necessary to calculate the smallest such \textbf{k}, that the plan it is weakly \textbf{k}-connected. The government plan calls weakly \textbf{k}-connected if the following condition: for any two different cities you can drive from one to another, violating the rules of the road no more than \textbf{k} times. Violation of the rules - this passage from an existing road in the opposite direction. It is guaranteed that between any two cities can be reached, perhaps several times violated the rules. \InputFile The first line of the input file are given two numbers, \textbf{2} ≤ \textbf{n} ≤ \textbf{300} и \textbf{1} ≤ \textbf{m} ≤ \textbf{10^5} - the number of cities and roads in the plan. The following \textbf{m} lines given by two numbers - numbers of cities, which begins and ends with the corresponding road. \OutputFile In the output file output minimum \textbf{k}, such that the input file plan is a weak \textbf{k}-connected.