На рисунке представлена схема дорог, связывающих города E, A, B, C, D, F, G, H, K, J, I, L. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Какова длина самого длинного пути из города E в город L? Длиной пути считать количество дорог, составляющих этот путь.
При решении будем каждый раз брать конкретную дорогу AB и смотреть, нет ли более длинного пути из A в B (Буквы приведены для примера).
1. Зачеркнём EB т.к. из E в B выгоднее пройти через EA-AB.
2. Зачеркнём BG, GF, BF, BC т.к. из B в F выгоднее пройти через BH-HC-CD-DF.
3. Зачеркнём FK, IL, JL т.к. из F в L выгоднее пройти через FI-IK-KL или через FJ-JK-KL.
Получаем путь EA-AB-BH-HC-CD-DF-FJ-FK-KL длиной 9.
Ответ: 9