C. Развороты графа
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Есть ориентированный граф, состоящий из $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$n$$$, и $$$m$$$ рёбер. В вершине $$$1$$$ находится фишка.

Разрешено совершать следующие действия:

  • Перемещение фишки. Переместить фишку можно из вершины $$$u$$$ в вершину $$$v$$$, если в графе присутствует ребро $$$u \to v$$$. Такое действие занимает $$$1$$$ секунду;
  • Разворот графа. Развернуть все рёбра в графе: каждое ребро $$$u \to v$$$ заменить на ребро $$$v \to u$$$. Каждое такое действие занимает всё больше и больше времени: первый разворот графа занимает $$$1$$$ секунду, второй — $$$2$$$ секунды, третий — $$$4$$$ секунды, $$$k$$$-й — $$$2^{k-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$$$.