В некоторой стране 225 городов и две авиакомпании. Авиалиниями каждой авиакомпании можно добраться от любого города до любого другого. Стоимость прямого перелёта между двумя городами составляет 2 тугрика, если они соединены единственной прямой авиалинией и 1 тугрик - если двумя. Стоимость маршрутов с пересадками складывается из отдельных участков.

Вася хочет добраться из города А в город В потратив как можно меньше денег. Какое наибольшее количество тугриков ему, тем не менее, может потребоваться?