广告

欢迎选手参加 APLSPC！

题目背景

众所周知，比赛数据都是比赛前一天晚上造好的。

不幸的是，大帝在 NFLSPC 前检查一个图论题的数据时，发现所有数据被邪恶的小 P 删除了前两行。

看着残缺的数据，大帝突然想知道，有多少种补全前两行的方式，使得数据合法，对 $998244353$ 取模。

因为大帝是大帝，所以大帝把输入文件给你，让你来解决这个问题。

大帝大发慈悲，决定保证至少存在一组合法的补全方式。

题目描述

给定若干行数据。求有多少个输入数据使得：

• 该数据删除前两行等于给定的若干行。
• 该数据完全满足原题的输入格式。

原题的输入格式如下：

第一行为一个正整数 $T$，接下来 $T$ 组数据。

每组数据的第一行为两个正整数 $n,m$。

接下来 $m$ 行，每行两个正整数 $u,v\ (1\leq u,v\leq n)$，描述一个图。

图可以不连通，可以有重边自环。

原题的数据范围为：

$1\le T \leq 2\times 10^5 $；

$1\le n,m \leq 2\times 10^5$。

输入格式

若干行 （不超过 $2\times10^5$ 行），每一行两个正整数

输出格式

一行，一个正整数，表示补全方案数对 $998244353$ 取模以后的结果。

样例输入 1

2 1
1 1

样例输出 1

199999

数据范围

对于所有数据：输入的所有数在 $[1,2\times10^5]$ 范围内，读入不超过 $2\times10^5$ 行。