F-筱玛爱语文_牛客练习赛49

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

题目描述

筱玛是一个热爱语文的好筱玛。在语文课上，老师带领同学们一起玩词语接龙。

作为语文素养大师，词语接龙这样简单的游戏当然不能满足筱玛。于是他想到了如下一个问题：

总共有 $n$ 个汉字，分别用整数 $1\sim n$ 表示。每个词语由两个汉字组成，这样总共有 $n^2$ 个词语。其中有 $m$ 个词语属于脏话，不能使用。

为了体现自己高超的语文素养，筱玛想知道，有多少种词语接龙的方案，使得所有的词语出现恰好一次。

第一行两个整数 $n,m$ 。

接下来 $m$ 行，每行两个整数 $a,b$ ，表示一个脏话。

一个整数表示答案，答案对 $998244353$ 取模。

示例1

复制

复制

一种合法的方案为： $(2,1)\to(1,1)\to(1,2)\to(2,2)\to(2,3)\to(3,3)$ 。

另一种合法的方案为： $(2,2)\to(2,1)\to(1,1)\to(1,2)\to(2,3)\to(3,3)$ 。

对于100%的测试数据，。