27722023-01-23 16:57:32CattTrükkcpp17Wrong answer 12/6085ms6612 KiB
#include <bits/stdc++.h>
using namespace std;
#define InTheNameOfGod ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
using ll = long long;

const int maxN = 2e5 + 5;
const int MOD = 1e9 + 7;


int power(int a, int b) {
    int res = 1;
    while(b > 0) {
        if(b % 2) res = (res * a) % MOD;
        a = (a*a) % MOD;
        b /= 2;
    }
    return res;
}


vector<vector<int> > g;
vector<int> c;

bool dfs(int x) {
    bool ret = 0;
    for(int sz : g[x]) {
        if(c[sz] == -1) {
            c[sz] = 1 - c[x];
            ret |= dfs(sz);
        }
        else if(c[sz] == c[x]) return true;
    }

    return ret;
}

int main() {
    int t;
    cin >> t;
    while(t--)
    {
        int n,m;
        cin >> n >> m;

        g.clear();
        g.resize(n+1);
        c.assign(n+1, -1);

        for(int i = 0; i < m; i++) {
            int x,y;
            cin >> x >> y;
            x--;
            g[x].push_back(y);
            g[y].push_back(x);
        }

        int comp = 0;
        bool b = 0;
        for(int i = 0; i <= n; i++) {
            if(c[i] == -1) {
                c[i] = 0;
                b |= dfs(i);
                comp++;
            }
        }

        if(b) cout <<"0\n";
        else {
            cout << power(2, comp-1) << "\n";
        }
    }
    return 0;
}
SubtaskSumTestVerdictTimeMemory
base12/60
1Accepted0/03ms1876 KiB
2Wrong answer0/041ms3468 KiB
3Accepted3/32ms2476 KiB
4Accepted3/32ms2304 KiB
5Accepted3/32ms2308 KiB
6Accepted3/32ms2440 KiB
7Wrong answer0/282ms5152 KiB
8Wrong answer0/282ms5460 KiB
9Wrong answer0/282ms5308 KiB
10Wrong answer0/282ms5476 KiB
11Wrong answer0/282ms5556 KiB
12Wrong answer0/285ms5816 KiB
13Wrong answer0/274ms5268 KiB
14Wrong answer0/274ms5460 KiB
15Wrong answer0/272ms5688 KiB
16Wrong answer0/272ms5668 KiB
17Wrong answer0/272ms5512 KiB
18Wrong answer0/272ms5512 KiB
19Wrong answer0/282ms6524 KiB
20Wrong answer0/282ms6612 KiB
21Wrong answer0/282ms6600 KiB
22Wrong answer0/282ms6340 KiB
23Wrong answer0/282ms6412 KiB
24Wrong answer0/282ms6416 KiB
25Wrong answer0/282ms6416 KiB
26Wrong answer0/272ms5952 KiB
27Wrong answer0/282ms6604 KiB
28Wrong answer0/279ms5896 KiB
29Wrong answer0/235ms5516 KiB
30Wrong answer0/235ms5632 KiB