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

Рассмотрим все возможные первые шаги из города А:

• Через Б: из Б можно попасть в К напрямую, через Д или через В. Получаем 3 пути: А–Б–К, А–Б–Д–К, А–Б–В–К.
• Через В: затем можно попасть в К. Получаем 1 путь: А–В–К.
• Через Г: можно попасть в К напрямую или через Е. Получаем 2 пути: А–Г–К, А–Г–Е–К.

Ответ: 6