Doctor Odd

Time Limit
1s
Memory Limit
131072KB
Judge Program
Standard
Ratio(Solve/Submit)
23.53%(4/17)
Description:

对于一个电影宇宙来说,一个完美的时间线总是是不可或缺的。MCU在这一方面一直做得非常优秀。但随着电影数目日益增多,很多的小bug也随之显现了出来,这一直困扰着编剧们组织剧情。但自从能随意操控时间的Doctor Strange走上银幕,编剧们便不再对此感到困扰,因为一旦有粉丝发现了新的时间线方面的漏铜,编剧们便会不假思索:“你瞧,就是那个披着红斗篷的大长脸干的”。Doctor Strange对此当然十分不满,但他正忙于在世界各地修建新的圣殿,用以保护地球的安全,没空理会那些莫名其妙的锅,但那些奇奇怪怪的锅却潜移默化地使得Doctor Strange变得越来越 odd……
这几天Doctor Strange打算在世界各地修建n座圣殿,用以保护地球的安全,但是由于人手严重不足,他必须要在这些圣殿之间建立m个传送门,以确保不会魔法的人们也能在紧急时刻通过传送门传送去另一个圣殿。每条传送门都是一条双向的通道连接着两端的两个圣殿。
此外,变得越来越odd的Doctor Strange还规定:若想某个传送门可以正常运作,还必须在其两端的两个圣殿内分别注入一些数值的魔法,并保证这两个圣殿的魔法值之和是 odd(奇数)
为了简化问题,每个圣殿内可能注入的魔法值数值只能为1、2或3。Doctor Strange虽是一位杰出的精神外科医生,但他对数学却并不是十分在行,所以他想来问你,他有多少种方法才能使得每一个传送门都可以正常运作。

Input:

输入包含多组测试数据,第一行为一个正整数 T (1 T 10) 表示有 T 组测试数据。
对于每组测试数据,
第一行包含两个正整数 n (1 n 105) 和 m (1 m 105),表示Doctor Strange打算修建 n 座圣殿,m条传送门。(圣殿编号为 1..n)
接下来m行,第i行包含两个正整数x和y,表示第i个传送门连接着编号为x和y的两座圣殿。

Output:

对于每组测试数据,
输出一行包含一个非零整数表示 $Doctor Strange$ 的总方案数。因为数字可能很大,请输出答案对 998244353 取模后的结果


Sample Input:
2
2 1
1 2
4 6
1 2
1 3
1 4
2 3
2 4
3 4
Sample Output:
4
0
Hint:

对于sample1: 四种方案分别为 {1, 2}, {3, 2}, {2, 1}, {2, 3} 对于 sample2: 不存在这样的方案


Submit