Sabotage Route

In Byteburg, an annual bicycle rally takes place through a network of intersections connected by one‐way streets. The street network forms a directed acyclic graph (DAG) with \( n \) intersections and \( m \) streets. Motorcyclists plan to sabotage the rally by blocking one intersection. Once an intersection is blocked, the cyclists must choose a new route that does not pass through that intersection. The motorcyclists’ aim is to block such an intersection that the longest route (measured as the number of streets) in the remaining network is as short as possible.

A route is defined as a sequence of intersections \( v_1, v_2, \dots, v_k \) such that there is a street from \( v_i \) to \( v_{i+1} \) for all \( 1 \le i < k \). The length of a route is the number of streets used (i.e. \( k-1 \)).

You are given the description of the DAG. Your task is to determine the minimum possible value of the longest route in the graph after removing exactly one intersection (and all streets incident to it).

Input Format:

• The first line contains two integers \( n \) and \( m \): the number of intersections and streets.
• Each of the next \( m \) lines contains two integers \( u \) and \( v \), representing a one‐way street from intersection \( u \) to intersection \( v \).

Output Format:

• Output a single integer: the minimum possible length of the longest route (measured in the number of streets) in the modified graph after removing one intersection.

Note: The graph is guaranteed to be acyclic.

inputFormat

The input is given as follows:

1. The first line contains two integers \( n \) and \( m \), where \( 1 \leq n \leq 1000 \) (for example) and \( 0 \leq m \leq 10,000 \).
2. Then follow \( m \) lines, each containing two integers \( u \) and \( v \) (\( 1 \leq u, v \leq n \)), indicating a one-way street from \( u \) to \( v \).

outputFormat

Output a single integer which is the minimum possible longest route length (in terms of the number of streets) when exactly one intersection is blocked.

sample

5 4
1 2
2 3
3 4
4 5

1