Graph Transpositions
Contest: VK Cup 2019-2020 - Final Round (Engine)
Difficulty rating: 2400
Tags: graphs, shortest paths

You are given a directed graph of $$$n$$$ vertices and $$$m$$$ edges. Vertices are numbered from $$$1$$$ to $$$n$$$. There is a token in vertex $$$1$$$.

The following actions are allowed:

- Token movement. To move the token from vertex $$$u$$$ to vertex $$$v$$$ if there is an edge $$$u \to v$$$ in the graph. This action takes $$$1$$$ second.
- Graph transposition. To transpose all the edges in the graph: replace each edge $$$u \to v$$$ by an edge $$$v \to u$$$. This action takes increasingly more time: $$$k$$$-th transposition takes $$$2^{k-1}$$$ seconds, i.e. the first transposition takes $$$1$$$ second, the second one takes $$$2$$$ seconds, the third one takes $$$4$$$ seconds, and so on.

The goal is to move the token from vertex $$$1$$$ to vertex $$$n$$$ in the shortest possible time. Print this time modulo $$$998\,244\,353$$$.

Input format:
The first line of input contains two integers $$$n, m$$$ ($$$1 \le n, m \le 200\,000$$$).

The next $$$m$$$ lines contain two integers each: $$$u, v$$$ ($$$1 \le u, v \le n; u \ne v$$$), which represent the edges of the graph. It is guaranteed that all ordered pairs $$$(u, v)$$$ are distinct.

It is guaranteed that it is possible to move the token from vertex $$$1$$$ to vertex $$$n$$$ using the actions above.

Output format:
Print one integer: the minimum required time modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
The first example can be solved by transposing the graph and moving the token to vertex $$$4$$$, taking $$$2$$$ seconds.

The best way to solve the second example is the following: transpose the graph, move the token to vertex $$$2$$$, transpose the graph again, move the token to vertex $$$3$$$, transpose the graph once more and move the token to vertex $$$4$$$.

Example input:
4 4
1 2
2 3
3 4
4 1

Example output:
2

Example input:
4 3
2 1
2 3
4 3

Example output:
10

Editorial:
Consider a sequence of actions that moves the token from vertex $$$1$$$ to vertex $$$n$$$. Let us say it has $$$A$$$ token movements and $$$B$$$ graph transpositions. This sequence takes $$$A + 2^{B} - 1$$$ seconds.
Note that the optimal path does not visit any edge twice. That means we need to consider only paths with $$$A \le m$$$. Consider another sequence consisting of $$$A'$$$ token movements and $$$B'$$$ graph transpositions. Let $$$lm = \lceil\log_2 m\rceil$$$. Note the following. If $$$B < lm < B'$$$ then $$$A + 2^{B} - 1$$$ < $$$A' + 2^{B'} - 1$$$. This is true because the difference between $$$A$$$ and $$$A'$$$ does not exceed $$$m$$$ and $$$2^{B'} - 2^{B} > m$$$. This gives us the following: if there is any sequence of actions with $$$B < lm$$$ that moves the token from vertex $$$1$$$ to vertex $$$n$$$ then optimal path's $$$B$$$ is less than $$$lm$$$ too. Let us check this with the following algorithm, and if it is so, find the optimal sequence of actions.
We can now build a new graph that consists of $$$lm$$$ copies of the original graph:
• Reverse all the edges in every even graph copy.
• For every vertex $$$u$$$ add new edge between $$$k$$$-th and $$$k+1$$$-th copies of vertex $$$u$$$ with weight $$$2^{k-1}$$$ for $$$k = 1 \ldots lm - 1$$$.
We can find optimal paths from the first copy of vertex $$$1$$$ to all the copies of vertex $$$n$$$ using Dijkstra algorithm. Shortest of these paths would correspond to the answer: movement along a copy of original edge denotes token movement; movement along a new edge denotes graph transposition.
If the algorithm found no paths, then the sequence of actions that moves the token to from vertex 1 to vertex $$$n$$$ consists of at least $$$lm + 1$$$ transpositions. Note that if $$$lm < B < B'$$$ then $$$A + 2^{B} - 1$$$ < $$$A' + 2^{B'} - 1$$$. It means that all sequences of actions can be compared using ordered vector $$$(B, A)$$$ lexicographically.
Let us build another graph consisting of $$$2$$$ copies of the original graph:
• Reverse all the edges in the second copy of the graph.
• Assign $$$(0, 1)$$$ to weights of all of these edges.
• For every vertex $$$u$$$ add two new edges between copies of $$$u$$$: from the first to the second copy and back. Weights of both edges is $$$(1, 0)$$$.
Let us find optimal paths from the first copy of vertex $$$1$$$ to both copies of vertex $$$n$$$ using Dijkstra algorithm. Let $$$(B, A)$$$ be the length of the shortest one. New graph allows us to restore the optimal sequence of actions that moves the token from vertex $$$1$$$ to vertex $$$n$$$ that will take $$$A + 2^{B} - 1$$$ seconds.