Permutation Composition

题号：NC282710
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

有 $m+1$ 个 $n$ 阶排列 $p_0\dots p_m$ 。

它们以如下方式生成：给定 $p_0,a_1\dots a_m,b_1\dots b_m$ 。则 $p_i$ 为 $p_{i-1}$ 中交换下标为 $a_i,b_i$ 的元素后的结果。

定义 $r=p\circ q$ 满足 $r_i=q_{p_i}$ 。

定义一个排列 $p$ 可被生成，当且仅当存在一个序列 $c_1\dots c_k$ 满足 $p=p_{c_1}\circ p_{c_2}\circ\dots\circ p_{c_k}$ 。

求可被生成的排列数量 $p$ 。答案对 $998244353$ 取模。

$1\le n\le 5\times 10^5,0\le m\le 5\times 10^5,1\le a_i,b_i\le n,a_i\neq b_i$ 。

输入描述:

第一行，两个整数，表示 。

第二行， 个整数，表示 。

接下来  行，每行两个整数，表示 。

输出描述:

一行，一个整数，表示答案。

示例1

输入

复制

5 0
2 1 4 5 3

输出

复制

示例2

输入

复制

6 1
2 1 4 3 6 5
1 3

输出

复制