题目链接：Beautiful Graph
题意：给定一张无向无权图，每个顶点可以赋值1,2,3，现要求相邻节点一奇一偶，求符合要求的图的个数。
题解：由于一奇一偶，需二分图判定，染色。判定失败，直接输出0。成功的话，统计下奇数（cnt1）和偶数（cnt2）顶点个数，只有奇数有两种，也就是说有$2^{cnt1}$种，但是可以把奇数和偶数顶点翻转，奇变偶，偶变奇，即最后有$2^{cnt1}+2^{cnt2}$种，注意此图可能不连通，各个图之间的答案数要相乘。
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
#include <fstream>
#include <iostream>
#include <algorithm>
using namespace std; #define eps 1e-8
#define pb push_back
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define clr(a,b) memset(a,b,sizeof(a)
#define FAST_IO ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) const int N=3e5+;
typedef long long ll;
typedef unsigned long long ull;
bool f;
int col[N];
ll p1=,p2=;
const ll mod=;
vector <int> E[N]; void dfs(int u){
if(col[u]==) p1++;
else p2++;
for(int i=;i<E[u].size();i++){
int v=E[u][i];
if(!col[v]){
if(col[u]==) col[v]=;
else if(col[u]==) col[v]=;
dfs(v);
}
else if(col[u]==col[v]) f=;
}
} ll fast_mod(ll a,ll b){
ll res=;
while(b){
if(b&) res=(res*a)%mod;
b>>=;
a=(a*a)%mod;
}
return res;
} int main(){
FAST_IO;
int t,n,m;
cin>>t;
while(t--){
f=;
ll ans=;
cin>>n>>m;
for(int i=;i<=m;i++){
int u,v;
cin>>u>>v;
E[u].push_back(v);
E[v].push_back(u);
}
for(int i=;i<=n;i++){
if(!col[i]){
col[i]=;
p1=;p2=;
dfs(i);
ans=ans*((fast_mod(,p1)+fast_mod(,p2))%mod)%mod;
}
}
if(!f) cout<<<<endl;
else cout<<ans<<endl;
for(int i=;i<=n;i++) E[i].clear(),col[i]=;
}
return ;
}