C-「LAOI-19」你存在的时空

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 荧：不论如何，我也绝对不愿错过五百年前与你重逢的机会。

$\hspace{15pt}$ 你百感交集，眼前明明是熟悉的亲人，她所说的这些却让你感到如此陌生。
$\hspace{15pt}$ 「你所说的这一切，你的计划，对我们而言真的有意义吗？」
$\hspace{15pt}$ 面对质疑，荧欲言又止。
$\hspace{15pt}$ 「从一开始，一切就只关乎你我。」

$\hspace{15pt}$ 随后，她将「新世界的经纬图」悬在手心，坎瑞亚所在的空间逐渐被纳入其中。在最后的时刻，你和妹妹对视着，陷入沉默。下一个瞬间，她，蒂莱尔，以及整个空间都已消失不见。你独自站在空旷的大地之上，一切似乎从未发生。

$\hspace{15pt}$ 在提瓦特的平行世界，为了找到血亲，你从时之执政处借得时空穿梭的权柄。你可以创造一个长为 $n$ 的序列 $a_1, a_2, \dots, a_n \left(1 \le a_i \le n\right)$ ，一次时空穿梭可以从第 $i$ 个时空出发，并到达第 $a_i$ 个时空。

$\hspace{15pt}$ 时之执政不希望发生时空悖论，所以时空穿梭的轨道不能交错。具体地：
$\hspace{23pt}\bullet\,$ 对于所有 $1 \le i < j \le n$ ，应有 $a_i \le a_j$ 。

$\hspace{15pt}$ 同时，她给出了 $m$ 条限制，具体地：
$\hspace{23pt}\bullet\,$ 第 $i$ 条限制给定 $x_i$ 和 $y_i$ ，要求 $a_{x_i}=y_i$ ；
$\hspace{15pt}$ 不保证 $x_i$ 互不相同，若限制出现冲突，则无合法的 $a$ 序列。

$\hspace{15pt}$ 你希望与自己的血亲重逢，所以时空穿梭会存在不完全的周期性。具体地：
$\hspace{23pt}\bullet\,$ 对于所有 $1 \le i \le n$ ，都应满足从第 $i$ 个时空出发，经过至少两次时空穿梭（ $i \to a_i \to a_{a_i} \to \cdots$ ）后，能够到达第 $a_i$ 个时空。

$\hspace{15pt}$ 出发之前，你想知道有多少种可能的结局，即存在多少满足上述所有条件的数组 $a$ 。由于答案可能很大，请将答案对 $998\,244\,353$ 取模后输出。

输入描述:

第一行输入两个整数 ，表示数组长度、限制个数。
此后  行，第  行输入两个整数 ，表示第  条限制。

输出描述:

如果不存在满足条件的  序列，直接输出 ；否则，输出一个整数，表示满足条件的  序列的数量对  取模后的结果。

示例1

输入

复制

2 1
1 2

输出

复制

说明

在这个样例中，合法的  序列有且仅有 。

示例2

输入

复制

3 0

输出

复制

说明

在这个样例中， 是不合法的，因为不存在 ，使得从  出发进行  次  操作终点为 。举例：从  出发，一次操作（最后一次操作为 ）后，终点为 ，两次操作（最后一次操作为 ）后，终点为 。

示例3

输入

复制

输出

复制

备注:

在几乎全部的情况下，PyPy 的运行速度优于 Python，我们建议您选择对应版本的 PyPy 进行提交、而不是 Python。