fork(1) download
copy 
  1.  
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define ll long long
  5. #define endl '\n'
  6. ll N = 1e9+7;
  7.  
  8. ll oo =1e13;
  9. const ll maxx = 1000000 + 3;
  10. ll n,m,k,q,x,y,z,l,r,mid,ans;
  11. vector<ll>vis,out;
  12. vector<vector<ll>>adj;
  13. bool imp=false;
  14. ll c1,c2;
  15. void BFS(ll st) {
  16.     queue<ll>q;
  17.  
  18.     q.push(st);
  19.     vis[st]=1;
  20.     out[st]=1;
  21.     c1++;
  22.     while (!q.empty()) {
  23.         ll cur = q.front();
  24.         q.pop();
  25.         for (auto x : adj[cur]) {
  26.             if (!vis[x]) {
  27.                 vis[x]=1;
  28.                 q.push(x);
  29.                 out[x]=3-out[cur];
  30.                 if (out[x] == 1)c1++;
  31.                 else c2++;
  32.             }
  33.             if (out[x]==out[cur]) imp = true;
  34.         }
  35.     }
  36. }
  37. ll fastpower(ll p,ll mod) {
  38.     if (p==0)return  1;
  39.     ll s = fastpower(p/2,mod) % mod;
  40.     s*=s;
  41.     s%=mod;
  42.     if (p & 1)s*=2;
  43.     s%=mod;
  44.     return s;
  45. }
  46. void solve() {
  47.     cin >> n >>m;
  48.     adj.assign(n+1,{});
  49.     vis.assign(n+1,0);
  50.     out.assign(n+1,0);
  51.  
  52.     for (ll i =0;i<m;i++) {
  53.         cin>>x>>y;
  54.         adj[x].push_back(y);
  55.         adj[y].push_back(x);
  56.     }
  57.     for (ll i =1;i<=n;i++) {
  58.         if (!vis[i]) {
  59.             c1=0,c2=0;
  60.             BFS(i);
  61.             ans=(ans*(fastpower(c1,998244353)%998244353+fastpower(c2,998244353)%998244353)%998244353)%998244353;
  62.         }
  63.     }
  64.     if (imp){cout<<0<<endl;}
  65.     else {
  66.         cout<<ans<<endl;
  67.     }
  68. }
  69. int main() {
  70.     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  71.     ll t=1 ;
  72.     cin >>t;
  73.     while (t--) {
  74.         ans=1;
  75.         solve();
  76.         imp =false;
  77.     }
  78. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
2
2 1
1 2
4 6
1 2
1 3
1 4
2 3
2 4
3 4
stdout
copy 
4
0
https://ideone.com/zIpg3g
language:
C++ (gcc 8.3)
created:
4 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!