Посчитать пути через букву Л

Привет! Давайте разбираться с этой задачей по шагам.

На картинке мы видим граф, вершины которого обозначены буквами и между некоторыми из них прочерчены стрелки, указывающие допустимое направление движения. Тебе нужно посчитать количество путей из города А в город М, которые проходят через город Л.

Вот как мы можем это сделать:

1. Сначала найдем все пути, ведущие в город Л. Пути должны начинаться из города А. Смотрим на граф и видим, что в город Л можно попасть из городов К и И.

   А) Чтобы попасть в город К из города А, мы можем пойти через города В и Ж или через города В, Е, Ж. Получается 2 варианта.

   Б) Чтобы попасть в город И из города А, мы можем пойти через города В, Г, З или через города В, Е, Г, З. Получается также 2 варианта.

   Всего путей в Л через К и И будет 2 + 2 = 4.

2. Теперь из города Л нужно добраться до города М. Мы видим, что можно пойти из Л в Н, а из Н в М. Также может быть вариант из Л в К, из К в Н и из Н в М. Но мы видим, что путь из Л в К невозможен из-за направления стрелок.

   Таким образом, мы имеем только один путь из Л в М: через Н.

3. Теперь умножаем количество путей