D

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <iostream>
#include <vector>
#include <string>
using namespace std;

#define u(n) (unsigned)n
#define int long long

vector <vector <int> > dp((int)(1e5) + 13, vector <int> (4));
vector <vector <int> > gr;
vector <int> used;
bool flag = true;
int sum = 0, mx = 0;
const int mod = 998244353;

void dfs(int v, int color, int d) {
    if (flag) {
        mx = max(mx, d);
        used[v] = color;
        for (int i:gr[v]) {
            if (!used[i]) {
                dfs(i, color % 2 + 1, d + 1);
            } else if (used[v] == used[i]){
                flag = false;
                break;
            };
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int n;
    cin >> n;
    dp[1][1] = 1;
    dp[1][2] = 1;
    dp[1][3] = 1;
    for (int i = 2; i < (int)(1e5) + 13; ++i) {
        dp[i][2] = (dp[i - 1][1] + dp[i - 1][3]) % mod;
        dp[i][1] = dp[i - 1][2];
        dp[i][3] = dp[i - 1][2];
    }
    for (int i = 0; i < n; ++i) {
        gr.clear();
        used.clear();
        flag = true;
        sum = 0;
        int N, M;
        cin >> N >> M;
        gr.resize(u(N) + 1);
        used.resize(u(N) + 1);
        for (int j = 0; j < M; ++j) {
            int u, v;
            cin >> u >> v;
            gr[u].push_back(v);
            gr[v].push_back(u);
        }
        dfs(1, 1, 1);
        if (!flag) {
            cout << 0 << '\n';
        } else {
            sum += ((dp[mx][1] + dp[mx][2]) % mod + dp[mx][3]) % mod;
            cout << sum << '\n';
        }
    }
}