CF1442C Graph Transpositions

题号：NC239223
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

给你一个 $n$ 个顶点和 $m$ 条边的有向图。顶点编号从 $1$ 到 $n$ 。顶点 $1$ 处有一个标记。

你可以进行以下两种操作：

- 移动标记：如果存在一条 $u\to v$ 的边，将标记从 $u$ 移动到 $v$ ，这个操作需要 $1$ 秒。
- 图翻转：翻转图上的所有边的方向，将图上**每一条边** $u\to v$ 替换为 $v\to u$ ，第 $k$ 次使用这个操作需要耗时 $2^{k-1}$ 秒。

你需要找到将标记从 $1$ 移动到 $n$ 的最短时间，请将答案对 $998,244,353$ 取模。

输入描述:

第一行两个整数，表示点数和边数。

接下来行每行两个整数，表示存在一条的有向边。

输出描述:

输出一个整数，表示答案对取模后的结果。

示例1

输入

复制

输出

复制

示例2

输入

复制

输出

复制

备注:

。

保证不存在重边并且至少存在一种从到的方案。