Односторонние трамваи: минимум поездок

В городе трамваи ходят по односторонним путям между остановками. За одну поездку можно проехать ровно по одному пути (из остановки u в остановку v).

Диспетчер хочет понять, за сколько поездок можно добраться от остановки s до остановки t, если выбирать маршрут умно. Если добраться нельзя — нужно честно сообщить об этом.

Формат ввода

В первой строке два целых числа n и m — количество остановок и количество односторонних путей. Далее в m строках записаны пары u v — есть путь из u в v. В последней строке два целых числа s и t.

Остановки пронумерованы от 1 до n.

Формат вывода

Выведите одно целое число:

• минимальное количество поездок, чтобы добраться из s в t,
• или -1, если это невозможно.

Ограничения

• 2 ≤ n ≤ 8000
• 0 ≤ m ≤ 8000
• 1 ≤ u, v, s, t ≤ n

Пример

Ввод:

5 6
1 2
2 3
3 5
1 4
4 5
2 4
1 5

Вывод:

2

Здесь каждая «поездка» — это проход по одному одностороннему пути, то есть по одному ребру графа. Все рёбра имеют одинаковую цену 1, значит минимальное число поездок — это кратчайшее расстояние по числу рёбер от s до t.

Для таких задач работает BFS (поиск в ширину): он идёт «слоями» — сначала все вершины на расстоянии 1, потом на расстоянии 2 и т.д. Поэтому первая найденная дистанция до вершины и есть минимальная.

План:

• Считай n, m и построй список смежности: для каждой остановки u храни все v, куда можно поехать напрямую.
• Заведи массив dist размера n+1, заполни -1 (значит «не посещали»).
• Положи s в очередь, поставь dist[s] = 0.
• Пока очередь не пуста:
• достань u;
• для каждого соседа v из g[u], если dist[v] == -1, то
• dist[v] = dist[u] + 1
• добавь v в очередь.
• Ответ: dist[t] (он останется -1, если доехать нельзя).

Мини-сниппет ключевого перехода: dist[v] = dist[u] + 1.

Сложность: O(n + m) по времени и O(n + m) по памяти — укладывается при n, m до 8000.

Частая ошибка: запускать DFS или пытаться «жадно» выбирать следующий путь — они не гарантируют минимум. В BFS важно помечать вершину посещённой сразу при добавлении в очередь, иначе можно положить её туда много раз.