← 返回题目列表

Codeforces · 1442/C

C. 图形转置

中文机器翻译题面 查看原题

给你一个由 $$$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$$$。