1. /*
  2.   FORHAD-SUST-BD
  3. */
  4. #include <iostream>
  5. #include <string>
  6. #include <map>
  7. #include <queue>
  8. #include <stack>
  9. #include <algorithm>
  10. #include <list>
  11. #include <set>
  12. #include <cmath>
  13. #include <cstring>
  14. #include <stdio.h>
  15. #include <string.h>
  16. #include <sstream>
  17. #include <stdlib.h>
  18. #include <vector>
  19. #include <iomanip>
  20.  
  21. using namespace std;
  22.  
  23. #ifdef __GNUC__
  24. typedef long long ll;typedef unsigned long long ull;
  25. #else
  26. typedef __int64 ll; typedef unsigned __int64 ull;
  27. #endif
  28.  
  29. #define INF 1<<28
  30. #define SIZE 100
  31. #define PI 2*acos(0)
  32. #define fg %I64d
  33. #define REP(i,n) for (i=0;i<n;i++)
  34. #define REV(i,n) for (i=n;i>=0;i--)
  35. #define FOR(i,p,k) for (i=p; i<k;i++)
  36. #define FOREACH(it,x) for(__typeof((x).begin()) it=(x.begin()); it!=(x).end(); ++it)
  37.  
  38. #define bug(x) cout<< "->" <<#x<<": "<<x<<endl
  39. #define Sort(x) sort(x.begin(),x.end())
  40. #define Reverse(x) reverse(x.begin(),x.end())
  41. #define MP(a,b) make_pair(a,b)
  42. #define Clear(x,with) memset(x,with,sizeof(x))
  43. #define Copy(c,r) memcpy(c,r,sizeof(r))
  44. #define SZ(x) (int)x.size()
  45. #define length(x) (int)x.length()
  46. #define All(x) x.begin(),x.end()
  47. #define pb push_back
  48. #define popcount(i) __builtin_popcount(i)
  49. #define gcd(a,b) __gcd(a,b)
  50. #define fs first
  51. #define sc second
  52. #define two(X) (1<<(X))
  53. #define twoL(X) (((int64)(1))<<(X))
  54. #define contain(S,X) (((S)&two(X))!=0)
  55. #define containL(S,X) (((S)&twoL(X))!=0)
  56.  
  57. typedef pair<int,int> pii;
  58. typedef pair<double,double> pdd;
  59. typedef vector<int> vi;
  60. typedef vector<double>vd;
  61. typedef vector<ll>vll;
  62. typedef vector<string> vs;
  63. typedef vector<vi>vvi;
  64. typedef vector<vll>vvll;
  65. typedef vector<vd>vvd;
  66. typedef vector<pii>vpii;
  67. typedef map<string,int> msi;
  68. typedef map<int,int>mii;
  69. typedef map<pii,int>mpi;
  70.  
  71. template<class T> inline T sqr(T x){return x*x;}
  72. template<class T> inline bool isPrime(T n){if(n<=1)return false;for (T i=2;i*i<=n;i++) if (n%i==0) return false;return true;}
  73. template<class T> inline T Mod(T n,T m) {return (n%m+m)%m;} //For Positive Negative No.
  74. template<class T> string toString(T n){ostringstream oss;oss<<n;oss.flush();return oss.str();}
  75. int toInt(string s){int r=0;istringstream sin(s);sin>>r;return r;}
  76. ll toLl(string s){ll r=0;istringstream sin(s); sin>>r; return r;}
  77. template<class T> void debug(const T& e){cout<<e<<endl;}
  78. template<class T1,class T2> void debug(const T1& e1,const T2& e2){cout<<e1<<"\t"<<e2<<endl;}
  79. template<class T1,class T2,class T3> void debug(const T1& e1,const T2& e2,const T3& e3){cout<<e1<<"\t"<<e2<<"\t"<<e3<<endl;}
  80. template<class T1,class T2,class T3,class T4> void debug(const T1& e1,const T2& e2,const T3& e3,const T4& e4){cout<<e1<<"\t"<<e2<<"\t"<<e3<<"\t"<<e4<<endl;}
  81. template<class T1,class T2,class T3,class T4,class T5> void debug(const T1& e1,const T2& e2,const T3& e3,const T4& e4,const T5& e5){cout<<e1<<"\t"<<e2<<"\t"<<e3<<"\t"<<e4<<"\t"<<e5<<endl;}
  82. template<class T> void debug(vector<T>& e){int i;REP(i,SZ(e)) cout<<e[i]<<" ";cout<<endl;}
  83. template<class T> void debug(vector< basic_string<T> >& e){int i,j;REP(i,SZ(e)) {REP(j,SZ(e[i])) cout<<e[i][j];cout<<endl;} cout<<endl;}
  84. template<class T> void debug(vector< vector<T> >& e){int i,j;REP(i,SZ(e)) {REP(j,SZ(e[i])) cout<<e[i][j]<<"\t";cout<<endl;} cout<<endl;}
  85. template<class T> void debug(T e[SIZE][SIZE],int row,int col){int i,j;REP(i,row) {REP(j,col) cout<<e[i][j]<<" ";cout<<endl;}}
  86.  
  87. ll Pow(ll B,ll P){ ll R=1; while(P>0) {if(P%2==1) R=(R*B);P/=2;B=(B*B);}return R;} //compute b^p
  88. //struct pq{ int cost,node;bool operator<(const pq &b)const{return cost>b.cost;}};// Min Priority Queue
  89. //bool comp(pq a,pq b){ return a.cost > b.cost;} //Comp Sort
  90.  
  91. //int dx[]={1,0,-1,0};int dy[]={0,1,0,-1}; //4 Direction
  92. //int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction
  93. //int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction
  94.  
  95. int mat[SIZE][SIZE],Color[SIZE],Nodes,check;
  96.  
  97. void dfs(int u)
  98. {
  99. int i;
  100.  
  101. REP(i,Nodes)
  102. {
  103. if(mat[u][i])
  104. {
  105. if(Color[i]==0)
  106. {
  107. Color[i]=Color[u]*(-1);
  108. dfs(i);
  109. }
  110. else if(Color[i]==Color[u])
  111. check=0;
  112. }
  113. }
  114. }
  115.  
  116. class Marketing
  117. {
  118. public:
  119. long long howMany(vector <string> compete)
  120. {
  121. ll i,sum=1,u,v;
  122.  
  123. Nodes=SZ(compete);
  124. Clear(mat,0);
  125. REP(i,Nodes)
  126. {
  127. istringstream iss(compete[i]);
  128. u=i;
  129. while(iss>>v)
  130. {
  131. mat[u][v]=mat[v][u]=1;
  132. }
  133. }
  134. Clear(Color,0);
  135. REP(i,Nodes)
  136. {
  137. if(Color[i]==0)
  138. {
  139. check=1;
  140. Color[i]=1;
  141. dfs(i);
  142. if(check)
  143. sum*=2;
  144. else return -1;
  145. }
  146. }
  147. return sum;
  148. }
  149. };
  150.  
  151.  
  152. template<typename T> void print( T a ) {
  153. cerr << a;
  154. }
  155.  
  156. void print( long long a ) {
  157. cerr << a << "L";
  158. }
  159.  
  160. void print( string a ) {
  161. cerr << '"' << a << '"';
  162. }
  163.  
  164. template<typename T> void print( vector<T> a ) {
  165. cerr << "{";
  166. for ( int i = 0 ; i != a.size() ; i++ ) {
  167. if ( i != 0 ) cerr << ", ";
  168. print( a[i] );
  169. }
  170. cerr << "}" << endl;
  171. }
  172.  
  173. template<typename T> void assert_eq( int n, T have, T need ) {
  174. if ( have == need ) {
  175. cerr << "Case " << n << " passed." << endl;
  176. } else {
  177. cerr << "Case " << n << " failed: expected ";
  178. print( need );
  179. cerr << " received ";
  180. print( have );
  181. cerr << "." << endl;
  182. }
  183. }
  184.  
  185. template<typename T> void assert_eq( int n, vector<T> have, vector<T> need ) {
  186. if( have.size() != need.size() ) {
  187. cerr << "Case " << n << " failed: returned " << have.size() << " elements; expected " << need.size() << " elements.";
  188. print( have );
  189. print( need );
  190. return;
  191. }
  192. for( int i= 0; i < have.size(); i++ ) {
  193. if( have[i] != need[i] ) {
  194. cerr << "Case " << n << " failed. Expected and returned array differ in position " << i << ".";
  195. print( have );
  196. print( need );
  197. return;
  198. }
  199. }
  200. cerr << "Case " << n << " passed." << endl;
  201. }
  202. void assert_eq( int n, string have, string need ) {
  203. if ( have == need ) {
  204. cerr << "Case " << n << " passed." << endl;
  205. } else {
  206. cerr << "Case " << n << " failed: expected ";
  207. print( need );
  208. cerr << " received ";
  209. print( have );
  210. cerr << "." << endl;
  211. }
  212. }
  213.  
  214. int main( int argc, char* argv[] )
  215. {
  216.  
  217. Marketing objectMarketing;
  218.  
  219. //test case0
  220. vector <string> param00;
  221. param00.push_back("1 4");
  222. param00.push_back("2");
  223. param00.push_back("3");
  224. param00.push_back("0");
  225. param00.push_back("");
  226. long long ret0 = objectMarketing.howMany(param00);
  227. long long need0 = 2;
  228. assert_eq(0,ret0,need0);
  229.  
  230. //test case1
  231. vector <string> param10;
  232. param10.push_back("1");
  233. param10.push_back("2");
  234. param10.push_back("0");
  235. long long ret1 = objectMarketing.howMany(param10);
  236. long long need1 = -1;
  237. assert_eq(1,ret1,need1);
  238.  
  239. //test case2
  240. vector <string> param20;
  241. param20.push_back("1");
  242. param20.push_back("2");
  243. param20.push_back("3");
  244. param20.push_back("0");
  245. param20.push_back("0 5");
  246. param20.push_back("1");
  247. long long ret2 = objectMarketing.howMany(param20);
  248. long long need2 = 2;
  249. assert_eq(2,ret2,need2);
  250.  
  251. //test case3
  252. vector <string> param30;
  253. param30.push_back("");
  254. param30.push_back("");
  255. param30.push_back("");
  256. param30.push_back("");
  257. param30.push_back("");
  258. param30.push_back("");
  259. param30.push_back("");
  260. param30.push_back("");
  261. param30.push_back("");
  262. param30.push_back("");
  263. param30.push_back("");
  264. param30.push_back("");
  265. param30.push_back("");
  266. param30.push_back("");
  267. param30.push_back("");
  268. param30.push_back("");
  269. param30.push_back("");
  270. param30.push_back("");
  271. param30.push_back("");
  272. param30.push_back("");
  273. param30.push_back("");
  274. param30.push_back("");
  275. param30.push_back("");
  276. param30.push_back("");
  277. param30.push_back("");
  278. param30.push_back("");
  279. param30.push_back("");
  280. param30.push_back("");
  281. param30.push_back("");
  282. param30.push_back("");
  283. long long ret3 = objectMarketing.howMany(param30);
  284. long long need3 = 1073741824;
  285. assert_eq(3,ret3,need3);
  286.  
  287. //test case4
  288. vector <string> param40;
  289. param40.push_back("1");
  290. param40.push_back("2");
  291. param40.push_back("3");
  292. param40.push_back("0");
  293. param40.push_back("5");
  294. param40.push_back("6");
  295. param40.push_back("4");
  296. long long ret4 = objectMarketing.howMany(param40);
  297. long long need4 = -1;
  298. assert_eq(4,ret4,need4);
  299.  
  300. }
  301.