Важная задача в теории графов — нахождение кратчайшего пути между вершинами. Тебе дан граф некоторой страны, где вершины это города, а рёбра — дороги, по которым можно путешествовать в обе стороны. Ты находишься в городе А. Какое минимальное количество промежуточных городов тебе нужно посетить, чтобы добраться до города В? Укажи количество промежуточных городов на кратчайшем пути из A в B (города A и B не учитывай).

Для нахождения минимального количества промежуточных городов на кратчайшем пути из города A в город B необходимо найти кратчайший путь между этими двумя городами. Количество промежуточных городов на этом пути будет равно количеству вершин на этом пути минус 2 (так как города A и B не учитываются).

Например, если кратчайший путь из города A в город B проходит через города C, D и E, то количество промежуточных городов будет равно 3 - 2 = 1.

Таким образом, количество промежуточных городов на кратчайшем пути из города A в город B равно количеству вершин на этом пути минус 2.