Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

dfs and similar

graphs

greedy

shortest paths

*2400

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Graph Transpositions

time limit per test

3 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputYou 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

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

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

Examples

Input

4 4 1 2 2 3 3 4 4 1

Output

2

Input

4 3 2 1 2 3 4 3

Output

10

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

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/21/2024 14:53:02 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|