Space Travel#7233
The infrastructure of a cosmic galaxy consists of planets and direct interplanetary routes, each connecting exactly two different planets. Given the vast distances in space, if there is no direct connection between two planets, transit planets are used for travel.
The popularity of a planet is defined as the number of pairs of different planets and for which a flight is only possible by passing through planet (, , k=1..N). For the given network of cosmic connections, determine the maximum popularity value and the number of planets that achieve this popularity.
The first line contains the natural numbers and (1 \leq N \leq 1000, 1 \leq M \leq 5000). The following lines each contain two natural numbers, describing a direct route between planets and (, j=1..N).
Provide the solution to the problem.
1-nji mysal