You are given a coordinated chart of n vertices and m edges. Vertices are numbered from 1 to n. There is a token in vertex 1. The accompanying activities are permitted: Token development. To move the token from vertex u to vertex v in case there is an edge u→v in
Correct answer will be upvoted else Multiple Downvoted. Don't submit random answer. Computer science.
You are given a coordinated chart of n vertices and m edges. Vertices are numbered from 1 to n. There is a token in vertex 1.
The accompanying activities are permitted:
Token development. To move the token from vertex u to vertex v in case there is an edge u→v in the chart. This activity requires 1 second.
Chart interpretation. To render every one of the edges in the diagram: supplant each edge u→v by an edge v→u. This activity requires some investment: k-th rendering requires 2k−1 seconds, for example the primary rendering requires 1 second, the subsequent one requires 2 seconds, the third one requires 4 seconds, etc.
The objective is to move the token from vertex 1 to vertex n in the most limited conceivable time. Print this time modulo 998244353.
Input
The primary line of input contains two integers n,m (1≤n,m≤200000).
The following m lines contain two integers each: u,v (1≤u,v≤n;u≠v), which address the edges of the chart. It is ensured that all arranged sets (u,v) are particular.
It is ensured that it is feasible to move the token from vertex 1 to vertex n utilizing the activities above.
Output
Print one integer: the base required time modulo 998244353.
Step by step
Solved in 4 steps with 1 images
