Eastest Magical Day Seep Group\'s Summer

Time Limit: 5000 ms Memory Limit: 65536 KiB

Problem Description

As we know, Tsuyuri Kumin likes sleeping in Eastest magical day sleep group\'s summer. But Rikka wants Kumin to play games with her. So she comes up with one problem:

Here is an undirected graph G with n vertices and m edges. Now you need to delete mn edges and to make sure that the remain graph is connected. Rikka wants you to tell her the number of ways to choose the edges.

Kumin wants to go to sleep, so she asks you to answer this question. Can you help her?

Input

There are at most 100 testcases,and there are no more 5 testcases with n10

For each test case, the first line contains two integers n,m (1n16,nmn(n1)2).

Then m lines follows. Each of them contains two integers ui,vi, meaning that there is an edge between ui and vi. It is guaranteed that the graph doesn\'t contain self loops or multiple edges.

Output

For each testcase print a single integer - the number of ways to choose the edges. The answer may be very large, so you only need to print the answer modulo 998244353.

Sample Input

4 5
1 2
2 3
3 4
4 1
1 3

Sample Output

5

Hint


Source

2015 Multi-University Training Contest 2