#pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("inline") #include using namespace std; template struct cLtraits_identity{ using type = T; } ; template using cLtraits_try_make_signed = typename conditional< is_integral::value, make_signed, cLtraits_identity >::type; void*wmem; char memarr[96000000]; template inline void walloc1d(T **arr, int x, void **mem = &wmem){ static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] ); (*arr)=(T*)(*mem); (*mem)=((*arr)+x); } template inline void walloc1d(T **arr, int x1, int x2, void **mem = &wmem){ walloc1d(arr, x2-x1, mem); (*arr) -= x1; } inline int my_getchar_unlocked(){ static char buf[1048576]; static int s = 1048576; static int e = 1048576; if(s == e && e == 1048576){ e = fread_unlocked(buf, 1, 1048576, stdin); s = 0; } if(s == e){ return EOF; } return buf[s++]; } inline void rd(int &x){ int k; int m=0; x=0; for(;;){ k = my_getchar_unlocked(); if(k=='-'){ m=1; break; } if('0'<=k&&k<='9'){ x=k-'0'; break; } } for(;;){ k = my_getchar_unlocked(); if(k<'0'||k>'9'){ break; } x=x*10+k-'0'; } if(m){ x=-x; } } struct MY_WRITER{ char buf[1048576]; int s; int e; MY_WRITER(){ s = 0; e = 1048576; } ~MY_WRITER(){ if(s){ fwrite_unlocked(buf, 1, s, stdout); } } } ; MY_WRITER MY_WRITER_VAR; void my_putchar_unlocked(int a){ if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){ fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout); MY_WRITER_VAR.s = 0; } MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a; } inline void wt_L(char a){ my_putchar_unlocked(a); } inline void wt_L(int x){ int s=0; int m=0; char f[10]; if(x<0){ m=1; x=-x; } while(x){ f[s++]=x%10; x/=10; } if(!s){ f[s++]=0; } if(m){ my_putchar_unlocked('-'); } while(s--){ my_putchar_unlocked(f[s]+'0'); } } template inline T pow_L(T a, S b){ T res = 1; res = 1; for(;;){ if(b&1){ res *= a; } b >>= 1; if(b==0){ break; } a *= a; } return res; } inline double pow_L(double a, double b){ return pow(a,b); } template inline T GCD_L(T a, U b){ T r; while(b){ r=a; a=b; b=r%a; } return a; } template inline S chmax(S &a, T b){ if(a has[100000]; int m[100000]; int p[100000][30]; int e[100000][30]; int arr[100000][30]; int k; int g; int tmp; int ress; int res[100000]; int ok[100000]; map ind; map mx; int s; int d[100]; int solve(int dep, int rem, int lis[], int st = 0, void *mem = wmem){ int i; if(rem == 0){ int j; wt_L(s); wt_L('\n'); for(j=(0);j<(s);j++){ int i; ress = 0; for(i=(0);i<(N);i++){ if(!ok[i] && has[i].count(d[j])==0){ res[ress++] = A[i]; ok[i] = 1; } } wt_L(ress); wt_L(' '); { int cTE1_r3A; if(ress==0){ wt_L('\n'); } else{ for(cTE1_r3A=(0);cTE1_r3A<(ress-1);cTE1_r3A++){ wt_L(res[cTE1_r3A]); wt_L(' '); } wt_L(res[cTE1_r3A]); wt_L('\n'); } } } return 1; } if(dep == s){ return 0; } int*nx; int sz; walloc1d(&nx, rem, &mem); for(i=(st);i<(k);i++){ int j; sz = 0; for(j=(0);j<(rem);j++){ if(has[lis[j]].count(i)){ nx[sz++] = lis[j]; } } if(sz == rem){ continue; } d[dep] = i; if(solve(dep+1, sz, nx, i+1, mem)){ return 1; } } return 0; } int main(){ int i; wmem = memarr; rd(N); for(i=(0);i<(N);i++){ rd(m[i]); { int a2conNHc; for(a2conNHc=(0);a2conNHc<(m[i]);a2conNHc++){ rd(p[i][a2conNHc]); rd(e[i][a2conNHc]); } } } for(i=(0);i<(N);i++){ int j; A[i] = 1; for(j=(0);j<(m[i]);j++){ A[i] *=(pow_L(p[i][j],e[i][j])); } } int ZIeRIny5; cLtraits_try_make_signed::type>::type iMWUTgY_; if(N==0){ iMWUTgY_ = 0; } else{ iMWUTgY_ = A[0]; for(ZIeRIny5=(1);ZIeRIny5<(N);ZIeRIny5++){ iMWUTgY_ = GCD_L(iMWUTgY_, A[ZIeRIny5]); } } g =iMWUTgY_; for(i=(0);i<(N);i++){ int j; for(j=(0);j<(m[i]);j++){ tmp = g; while(tmp % p[i][j] == 0){ tmp /= p[i][j]; e[i][j]--; } } } for(i=(0);i<(N);i++){ int j; for(j=(0);j<(m[i]);j++){ if(e[i][j]){ if(ind.count(p[i][j]) == 0){ ind[p[i][j]] = k++; } chmax(mx[p[i][j]], e[i][j]); } } } for(i=(0);i<(N);i++){ int j; for(j=(0);j<(m[i]);j++){ if(e[i][j] && mx[p[i][j]] == e[i][j]){ has[i].insert(ind[p[i][j]]); } } } for(i=(0);i<(N);i++){ if(has[i].size() == k){ wt_L(-1); wt_L('\n'); return 0; } } for(s=2;;s++){ int lis[N]; for(i=(0);i<(N);i++){ lis[i] = i; } if(solve(0, N, lis)){ break; } } return 0; } // cLay version 20210926-1 // --- original code --- // int N, A[1d5]; set has[]; // int m[1d5], p[1d5][30], e[1d5][30], arr[1d5][30], k, g, tmp; // int ress, res[1d5], ok[]; // map ind, mx; // // int s, d[100]; // // int solve(int dep, int rem, int lis[], int st = 0, void *mem = wmem){ // if(rem == 0){ // wt(s); // rep(j,s){ // ress = 0; // rep(i,N) if(!ok[i] && has[i].count(d[j])==0) res[ress++] = A[i], ok[i] = 1; // wt(ress, res(ress)); // } // return 1; // } // if(dep == s) return 0; // // int *nx, sz; // walloc1d(&nx, rem, &mem); // rep(i,st,k){ // sz = 0; // rep(j,rem) if(has[lis[j]].count(i)) nx[sz++] = lis[j]; // if(sz == rem) continue; // d[dep] = i; // if(solve(dep+1, sz, nx, i+1, mem)) return 1; // } // return 0; // } // // { // rd(N); // rep(i,N) rd(m[i],(p[i],e[i])(m[i])); // rep(i,N){ // A[i] = 1; // rep(j,m[i]) A[i] *= p[i][j]**e[i][j]; // } // g = gcd(A(N)); // rep(i,N) rep(j,m[i]){ // tmp = g; // while(tmp % p[i][j] == 0) tmp /= p[i][j], e[i][j]--; // } // rep(i,N) rep(j,m[i]) if(e[i][j]){ // if(ind.count(p[i][j]) == 0) ind[p[i][j]] = k++; // mx[p[i][j]] >?= e[i][j]; // } // rep(i,N) rep(j,m[i]) if(e[i][j] && mx[p[i][j]] == e[i][j]) has[i].insert(ind[p[i][j]]); // rep(i,N) if(has[i].size() == k) wt(-1), return 0; // // for(s=2;;s++){ // int lis[N]; // rep(i,N) lis[i] = i; // if(solve(0, N, lis)) break; // } // }