CF1442C.Graph Transpositions

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$.

给你一个包含 $n$ 个顶点和 $m$ 条有向边的有向图。顶点编号为 $1$ 到 $n$。初始时，一个标记（token）位于顶点 $1$。

允许执行以下两种操作：

• 标记移动：若图中存在一条从顶点 $u$ 指向顶点 $v$ 的边 $u \to v$，则可将标记从 $u$ 移动到 $v$。该操作耗时 $1$ 秒。
• 图转置：将图中所有边的方向翻转：即把每条边 $u \to v$ 替换为边 $v \to u$。该操作的耗时随执行次数递增：第 $k$ 次转置耗时 $2^{k-1}$ 秒，即第一次转置耗时 $1$ 秒，第二次耗时 $2$ 秒，第三次耗时 $4$ 秒，依此类推。

目标是将标记从顶点 $1$ 移动到顶点 $n$，并使总耗时最短。请输出该最短耗时对 $998\,244\,353$ 取模的结果。

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.

输入的第一行包含两个整数 $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$。

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

输出一个整数：最小所需时间对 $998\,244\,353$ 取模的结果。

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$.

第一个示例可通过转置图并将棋子移动到顶点 $4$ 来解决，耗时 $2$ 秒。

解决第二个示例的最优方法如下：转置图，将棋子移动到顶点 $2$；再次转置图，将棋子移动到顶点 $3$；再进行一次图转置，最后将棋子移动到顶点 $4$。