P2185 Highway Toll Stamp

In the country of PALMIA, there are $N$ cities connected by roads (each road connects exactly two cities bidirectionally). From any city, it is possible to reach every other city by traveling along one or more roads. Starting this year, a highway toll will be charged. In the middle of each road, there is a tax collector who collects 1 PALMIA COIN (1 PC) from every car that uses this road. Government officials decided to reduce the number of tax collectors by introducing a road stamp. If a car wants to enter a road, it must stick this stamp on its window. The officials set the annual road stamp value to be equal to the total cost of making $100$ trips between the two farthest cities. The distance between two cities is defined as the minimum number of roads that must be traversed to get from one city to the other. Your task is to write a program to compute the value of the road stamp.

The input contains multiple test cases. The first line of each test case contains two integers $N$ and $M$ (separated by a space), where $N$ is the number of cities and $M$ is the number of roads ($1 \le N \le 1000$, $1 \le M \le 25000$). Cities are labeled with integers from $1$ to $N$. Each of the next $M$ lines contains a pair of integers $A$, $B$ ($1 \le A, B \le N$), separated by a space, indicating that there is a road between city $A$ and city $B$. The input terminates with a line containing two zeros separated by a space.

For each test case, output one line containing the value of the road stamp.

Translated by ChatGPT 5