#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;
ll power(ll a, ll b) {
ll 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]) ret = 1;
}
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;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 60/60 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1876 KiB | |||
2 | Elfogadva | 0/0 | 41ms | 3464 KiB | |||
3 | Elfogadva | 3/3 | 2ms | 2324 KiB | |||
4 | Elfogadva | 3/3 | 2ms | 2348 KiB | |||
5 | Elfogadva | 3/3 | 2ms | 2472 KiB | |||
6 | Elfogadva | 3/3 | 2ms | 2724 KiB | |||
7 | Elfogadva | 2/2 | 83ms | 5444 KiB | |||
8 | Elfogadva | 2/2 | 82ms | 5388 KiB | |||
9 | Elfogadva | 2/2 | 82ms | 5348 KiB | |||
10 | Elfogadva | 2/2 | 82ms | 5344 KiB | |||
11 | Elfogadva | 2/2 | 82ms | 5344 KiB | |||
12 | Elfogadva | 2/2 | 83ms | 5628 KiB | |||
13 | Elfogadva | 2/2 | 74ms | 4904 KiB | |||
14 | Elfogadva | 2/2 | 74ms | 4904 KiB | |||
15 | Elfogadva | 2/2 | 72ms | 5032 KiB | |||
16 | Elfogadva | 2/2 | 72ms | 5620 KiB | |||
17 | Elfogadva | 2/2 | 72ms | 5456 KiB | |||
18 | Elfogadva | 2/2 | 72ms | 5480 KiB | |||
19 | Elfogadva | 2/2 | 82ms | 6500 KiB | |||
20 | Elfogadva | 2/2 | 82ms | 6828 KiB | |||
21 | Elfogadva | 2/2 | 82ms | 6908 KiB | |||
22 | Elfogadva | 2/2 | 82ms | 6732 KiB | |||
23 | Elfogadva | 2/2 | 82ms | 6520 KiB | |||
24 | Elfogadva | 2/2 | 83ms | 6908 KiB | |||
25 | Elfogadva | 2/2 | 82ms | 6976 KiB | |||
26 | Elfogadva | 2/2 | 72ms | 6204 KiB | |||
27 | Elfogadva | 2/2 | 83ms | 6848 KiB | |||
28 | Elfogadva | 2/2 | 79ms | 6576 KiB | |||
29 | Elfogadva | 2/2 | 35ms | 5888 KiB | |||
30 | Elfogadva | 2/2 | 37ms | 5884 KiB |