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

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

Difficulty: HARD

Starter code:

Solutions:
from heapq import heappush, heappop
mod = 998244353
(N, M) = map(int, input().split())
E1 = [[] for _ in range(N)]
E2 = [[] for _ in range(N)]
for _ in range(M):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	E1[u].append(v)
	E2[v].append(u)
mask1 = (1 << 23) - 1
mask2 = (1 << 18) - 1
inf = 1 << 62
dist = [inf] * (1 << 23)
start = 0
dist[start] = 0
q = [start]
while q:
	v = heappop(q)
	dist_v = v >> 23
	v &= mask1
	n_trans = v >> 18
	v_node = v & mask2
	if v_node == N - 1:
		print(dist_v % mod)
		exit()
	if n_trans > 20:
		break
	if dist[v] != dist_v:
		continue
	for u_node in E1[v_node] if n_trans & 1 == 0 else E2[v_node]:
		u = n_trans << 18 | u_node
		dist_u = dist_v + 1
		if dist_u < dist[u]:
			dist[u] = dist_u
			heappush(q, dist_u << 23 | u)
	u = n_trans + 1 << 18 | v_node
	dist_u = dist_v + (1 << n_trans)
	if dist_u < dist[u]:
		dist[u] = dist_u
		heappush(q, dist_u << 23 | u)
mask1 = (1 << 37) - 1
mask2 = (1 << 19) - 1
mask3 = (1 << 18) - 1
REV = 1 << 18
dist = [inf] * (1 << 19)
start = 0
dist[start] = 0
q = [start]
while q:
	v = heappop(q)
	dist_v = v >> 19
	n_trans = dist_v >> 18
	v &= mask2
	v_node = v & mask3
	if v_node == N - 1:
		ans = pow(2, n_trans, mod) - 1 + (dist_v & mask3)
		print(ans)
		exit()
	rev = v & REV
	if dist[v] != dist_v:
		continue
	for u_node in E1[v_node] if n_trans & 1 == 0 else E2[v_node]:
		u = rev | u_node
		dist_u = dist_v + 1
		if dist_u < dist[u]:
			dist[u] = dist_u
			heappush(q, dist_u << 19 | u)
	u = v ^ REV
	dist_u = dist_v + (1 << 18)
	if dist_u < dist[u]:
		dist[u] = dist_u
		heappush(q, dist_u << 19 | u)
assert False


import sys, io, os
BUFSIZE = 8192

class FastIO(io.IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = io.BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(io.IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from heapq import heappush, heappop
mod = 998244353
(N, M) = map(int, input().split())
E1 = [[] for _ in range(N)]
E2 = [[] for _ in range(N)]
for _ in range(M):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	E1[u].append(v)
	E2[v].append(u)
mask1 = (1 << 23) - 1
mask2 = (1 << 18) - 1
inf = 1 << 62
dist = [inf] * (1 << 23)
start = 0
dist[start] = 0
q = [start]
while q:
	v = heappop(q)
	dist_v = v >> 23
	v &= mask1
	n_trans = v >> 18
	v_node = v & mask2
	if v_node == N - 1:
		print(dist_v % mod)
		exit()
	if n_trans > 20:
		break
	if dist[v] != dist_v:
		continue
	for u_node in E1[v_node] if n_trans & 1 == 0 else E2[v_node]:
		u = n_trans << 18 | u_node
		dist_u = dist_v + 1
		if dist_u < dist[u]:
			dist[u] = dist_u
			heappush(q, dist_u << 23 | u)
	u = n_trans + 1 << 18 | v_node
	dist_u = dist_v + (1 << n_trans)
	if dist_u < dist[u]:
		dist[u] = dist_u
		heappush(q, dist_u << 23 | u)
mask1 = (1 << 37) - 1
mask2 = (1 << 19) - 1
mask3 = (1 << 18) - 1
REV = 1 << 18
dist = [inf] * (1 << 19)
start = 0
dist[start] = 0
q = [start]
while q:
	v = heappop(q)
	dist_v = v >> 19
	n_trans = dist_v >> 18
	v &= mask2
	v_node = v & mask3
	if v_node == N - 1:
		ans = pow(2, n_trans, mod) - 1 + (dist_v & mask3)
		print(ans)
		exit()
	rev = v & REV
	if dist[v] != dist_v:
		continue
	for u_node in E1[v_node] if n_trans & 1 == 0 else E2[v_node]:
		u = rev | u_node
		dist_u = dist_v + 1
		if dist_u < dist[u]:
			dist[u] = dist_u
			heappush(q, dist_u << 19 | u)
	u = v ^ REV
	dist_u = dist_v + (1 << 18)
	if dist_u < dist[u]:
		dist[u] = dist_u
		heappush(q, dist_u << 19 | u)
assert False


import sys
input = sys.stdin.readline
import heapq
mod = 998244353
(n, m) = list(map(int, input().split()))
E = [[] for i in range(n + 1)]
E2 = [[] for i in range(n + 1)]
for i in range(m):
	(x, y) = list(map(int, input().split()))
	E[x].append(y)
	E2[y].append(x)
TIME = [1 << 29] * (n + 1)
TIME[1] = 0

def shuku(x, y):
	return (x << 20) + y
Q = []
ANS = []
for k in range(n + 1):
	NQ = []
	if k <= 1:
		heapq.heappush(Q, shuku(0, 1))
	if k % 2 == 0:
		while Q:
			x = heapq.heappop(Q)
			time = x >> 20
			town = x - (time << 20)
			if TIME[town] < time:
				continue
			for to in E[town]:
				if TIME[to] > time + 1:
					TIME[to] = time + 1
					heapq.heappush(Q, shuku(TIME[to], to))
					heapq.heappush(NQ, shuku(TIME[to], to))
	else:
		while Q:
			x = heapq.heappop(Q)
			time = x >> 20
			town = x - (time << 20)
			if TIME[town] < time:
				continue
			for to in E2[town]:
				if TIME[to] > time + 1:
					TIME[to] = time + 1
					heapq.heappush(Q, shuku(TIME[to], to))
					heapq.heappush(NQ, shuku(TIME[to], to))
	Q = NQ
	ANS.append(TIME[n])
	if k >= 100 and TIME[n] != 1 << 29:
		break
A = ANS[0]
for k in range(1, len(ANS)):
	if ANS[k] == 1 << 29:
		continue
	if ANS[k - 1] == 1 << 29:
		A = (ANS[k] + pow(2, k, mod) - 1) % mod
	if k < 60 and ANS[k - 1] - ANS[k] > pow(2, k - 1):
		A = (ANS[k] + pow(2, k, mod) - 1) % mod
print(A)


import os
import sys
from io import BytesIO, IOBase
pow2 = [1]
for i in range(30):
	pow2.append(pow2[-1] * 2)

class distance(object):

	def __init__(self, val1: int, val2: int):
		self.val1 = val1
		self.val2 = val2

	def __repr__(self):
		return f'Node value: {(self.val1, self.val2)}'

	def __lt__(self, other):
		a = self.val1
		b = self.val2
		c = other.val1
		d = other.val2
		if a == c and b < d:
			return True
		elif a == c and b >= d:
			return False
		elif a < c and c >= 30:
			return True
		elif a > c and a >= 30:
			return False
		elif pow2[a] + b < pow2[c] + d:
			return True
		elif pow2[a] + b >= pow2[c] + d:
			return False
		else:
			return False

class distance2(object):

	def __init__(self, val1: int, val2: int):
		self.val1 = val1
		self.val2 = val2

	def __repr__(self):
		return f'Node value: {(self.val1, self.val2)}'

	def __lt__(self, other):
		a = self.val1
		b = self.val2
		c = other.val1
		d = other.val2
		if a == c and b < d:
			return True
		elif a == c and b >= d:
			return False
		elif a < c:
			return True
		elif a > c:
			return False
		else:
			return False
from heapq import heappush, heappop

def main():
	MOD = 998244353
	(n, m) = map(int, input().split())
	graph = []
	for _ in range(n):
		graph.append([])
		graph.append([])
	for _ in range(m):
		(u, v) = map(int, input().split())
		graph[2 * u - 2].append(2 * v - 2)
		graph[2 * v - 1].append(2 * u - 1)
	for i in range(n):
		graph[2 * i].append(2 * i + 1)
		graph[2 * i + 1].append(2 * i)
	INF = 10 ** 9
	dist = [distance(INF, INF)] * (2 * n)
	dist[0] = distance(0, 0)
	node = [(dist[0], 0)]
	isVisited = [False] * (2 * n)
	while node:
		(dista, curV) = heappop(node)
		if isVisited[curV]:
			continue
		isVisited[curV] = True
		for newV in graph[curV]:
			if (curV - newV) % 2 == 0:
				newDist = distance(dist[curV].val1, dist[curV].val2 + 1)
				if newDist < dist[newV]:
					dist[newV] = newDist
					heappush(node, (newDist, newV))
			else:
				newDist = distance(dist[curV].val1 + 1, dist[curV].val2)
				if newDist < dist[newV]:
					dist[newV] = newDist
					heappush(node, (newDist, newV))
	dist1 = min(dist[2 * n - 1], dist[2 * n - 2])
	dist = [distance2(INF, INF)] * (2 * n)
	dist[0] = distance2(0, 0)
	node = [(dist[0], 0)]
	isVisited = [False] * (2 * n)
	while node:
		(dista, curV) = heappop(node)
		if isVisited[curV]:
			continue
		isVisited[curV] = True
		for newV in graph[curV]:
			if (curV - newV) % 2 == 0:
				newDist = distance2(dist[curV].val1, dist[curV].val2 + 1)
				if newDist < dist[newV]:
					dist[newV] = newDist
					heappush(node, (newDist, newV))
			else:
				newDist = distance2(dist[curV].val1 + 1, dist[curV].val2)
				if newDist < dist[newV]:
					dist[newV] = newDist
					heappush(node, (newDist, newV))
	dist2 = min(dist[2 * n - 1], dist[2 * n - 2])
	dist2N = distance(dist2.val1, dist2.val2)
	if dist1 < dist2N:
		print((pow(2, dist1.val1, MOD) + dist1.val2 - 1) % MOD)
	else:
		print((pow(2, dist2N.val1, MOD) + dist2N.val2 - 1) % MOD)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()