Weak k-connectivity#2204
Anya, as a future world champion in programming, was assigned a very important task. The Government of the N-region gives her a plan for constructing roads between cities. According to the plan, all roads are one-way, but there may be multiple roads between any two cities, possibly in different directions. Anya needs to calculate the smallest integer such that the plan is weakly -connected.
A plan is called weakly -connected if the following holds: for any two different cities, it is possible to travel from one to the other, violating the rules of the road no more than times. A rule violation means traveling along an existing road in the opposite direction. It is guaranteed that it is possible to travel between any two cities, possibly violating the rules several times.
The first line contains two integers, 2 \le n \le 300 and 1 \le m \le 10^5 — the number of cities and roads in the plan. Each of the next lines contains two integers — the numbers of the cities where the corresponding road starts and ends.
Output the minimal such that the plan given in the input is weakly -connected.
Example 1