给你一个由 $$$n$$$ 个顶点和 $$$m$$$ 个边组成的有向图。顶点编号从 $$$1$$$ 到 $$$n$$$。顶点 $$$1$$$ 中有一个令牌。
允许执行以下操作:
- 代币移动。如果图中存在边 $$$u \to v$$$,则将标记从顶点 $$$u$$$ 移动到顶点 $$$v$$$。此操作需要 $$$1$$$ 秒。
- 图转置。要转置图中的所有边:将每条边 $$$u \to v$$$ 替换为边 $$$v \to u$$$。此操作需要的时间越来越长:第 $$$k$$$ 次换位需要 $$$2^{k-1}$$$ 秒,即第一次换位需要 $$$1$$$ 秒,第二个需要 $$$2$$$ 秒,第三个需要 $$$4$$$ 秒,依此类推。
目标是在尽可能短的时间内将令牌从顶点 $$$1$$$ 移动到顶点 $$$n$$$。打印这次对 $$$998\,244\,353$$$ 取模的时间。
输入
输入的第一行包含两个整数 $$$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$$$。
输出
打印一个整数:所需的最短时间模 $$$998\,244\,353$$$。
示例
输入 #1
4 4 1 2 2 3 3 4 4 1
输出 #1
2
输入 #2
4 3 2 1 2 3 4 3
输出 #2
10
注意
第一个示例可以通过转置图并将令牌移动到顶点 $$$4$$$ 来解决,需要 $$$2$$$ 秒。
解决第二个示例的最佳方法如下:转置图,将标记移动到顶点 $$$2$$$,再次转置图,将标记移动到顶点 $$$3$$$,再次转置图并将标记移动到顶点 $$$4$$$。