Есть ориентированный граф, состоящий из $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$n$$$, и $$$m$$$ рёбер. В вершине $$$1$$$ находится фишка.
Разрешено совершать следующие действия:
Цель состоит в том, чтобы переместить фишку из вершины $$$1$$$ в вершину $$$n$$$ за минимально возможное время. Выведите это время по модулю $$$998\,244\,353$$$.
В первой строке дано два целых числа $$$n, m$$$ ($$$1 \le n, m \le 200\,000$$$).
В следующих $$$m$$$ строках даны пары чисел $$$u, v$$$ ($$$1 \le u, v \le n; u \ne v$$$), обозначающие рёбра графа. Гарантируется, что все пары $$$(u, v)$$$ различны.
Гарантируется, что возможно переместить фишку из вершины $$$1$$$ в вершину $$$n$$$ в помощью действий выше.
Выведите одно число — минимальное требуемое время по модулю $$$998\,244\,353$$$.
4 4 1 2 2 3 3 4 4 1
2
4 3 2 1 2 3 4 3
10
В первом примере достаточно развернуть граф и переместить фишку в вершину $$$4$$$, что в сумме займёт $$$2$$$ секунды.
Во втором примере оптимальная стратегия следующая: развернуть граф, переместить фишку в вершину $$$2$$$, снова развернуть граф, переместить фишку в вершину $$$3$$$, ещё раз развернуть граф и переместить фишку в вершину $$$4$$$.
Название |
---|