fork 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.  
  79. /*
  80.  
  81. Latvia was never a country on my radar, but I spent a weekend in Riga for the Women in Fly to Riga and back in less than 100 dollars”, “celebrate stag party with your friends”, “order erotic massages in the best lounges of the city” were tempting appeals for many British, Irish, Swedish, Finnish, German and Benelux men and Riga has no shortage of sex tourism
  82.  
  83.  
  84. */
  85. }
Success #stdin #stdout 0s 5324KB
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/yJ3ubb
language:
C++ (gcc 8.3)
created:
2 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!