fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5. const ll MOD = 1e9 + 7;
  6. ll power(ll a,ll b){
  7. 	ll ans = 1;
  8. 	while(b>0){
  9. 		if(b&1){
  10. 			ans = (ans*a)%MOD;
  11. 		}
  12.  
  13. 		a = (a*a)%MOD;
  14. 		b>>=1;
  15. 	}
  16. 	return ans;
  17. }
  18. int main() {
  19.     ll n ;
  20.     ll m;
  21.     ll k;
  22.     cin>>n>>m>>k;
  23.  
  24.     vector<ll>G[n+1];
  25.  
  26.     for(int i = 1 ; i<=m ;i++){
  27.     	int u,v;
  28.     	cin>>u>>v;
  29.     	G[u].push_back(v);
  30.     	G[v].push_back(u);
  31.     }
  32.     int red=0 , blue = 0;
  33.     vector<int>used(n+1);
  34.     queue<ll>q;
  35.     used[1]=1;
  36.     q.push(1);red++;
  37.     bool ans = true;
  38.  
  39.     //int k = n*m -count;
  40.     while(!q.empty()){
  41.     	auto u = q.front();
  42.     	q.pop();
  43.  
  44.     	for(auto v : G[u]){
  45.     		if(used[v] == 0){
  46.     			if(used[u] == 1){
  47.     			used[v]=3;
  48.  
  49.     			blue++;
  50.     		}else if(used[u] == 3){
  51.     				used[v] = 1;
  52.     				red++;
  53.     		}
  54.     		q.push(v);
  55.     	}else{
  56.     	  if(used[u]+used[v] != 4){
  57.     		ans = false;
  58.     	}	
  59.     	}}
  60.  
  61.  
  62.     }
  63.  
  64.     ll t2 = k/3;
  65.     ll t1  = k - t2;
  66.  
  67.    if (ans == false){
  68.    	cout<<"no";
  69.    }else{
  70.    	cout<<red <<" "<<blue<<endl;
  71.    	 cout<< ((1LL*power(t2,red)*power(t1,blue))%MOD+(1LL*power(t1,red)*power(t2,blue))%MOD)%MOD;
  72.    }
  73. 	return 0;
  74. }
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
4 4 6
1 2
2 3
3 4
4 1
stdout
copy 
2 2
128
https://ideone.com/3N6B5N
language:
C++ (gcc 8.3)
created:
7 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!