Statement

The best thing about online programming contests is that you don't need to set up an actual server, you just connect to your online server and then install what you need. For offline contests, instead, you are often faced with the hard reality: servers break, burst into flames, and you always need to replace parts. Having prepared a lot of offline contests, William and Giorgio know full well how boring these "chores" can be, so they are now trying to predict how much time will be lost to them. The main problem, is that you don't know in advance where you will need to go: it may be possible that the parts you need are located in some far away city, and retrieving them may take a long time. Furthermore, the contest venue may be decided at the last minute, so we don't even know in advance which city will host the contest! Luckily, Giorgio has a map of all the cities and a selected set of roads (the "best" ones), so that there is exactly one path between any two cities following the map...