#include #include #include #define MT_N 624 #define MT_M 397 #define MT_MATRIX_A 0x9908b0dfUL #define MT_UPPER_MASK 0x80000000UL #define MT_LOWER_MASK 0x7fffffffUL static unsigned int mt[MT_N]; static int mti = MT_N + 1; void init_genrand(unsigned int s) { mt[0] = s & 0xffffffffUL; for (mti = 1; mti < MT_N; mti++) { mt[mti] = (1812433253UL * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti); mt[mti] &= 0xffffffffUL; } } unsigned int genrand() { unsigned int y; static unsigned int mag01[2] = {0x0UL, MT_MATRIX_A}; if (mti >= MT_N) { int kk; if (mti == MT_N + 1) init_genrand(5489UL); for (kk = 0; kk < MT_N - MT_M; kk++) { y = (mt[kk] & MT_UPPER_MASK) | (mt[kk+1] & MT_LOWER_MASK); mt[kk] = mt[kk+MT_M] ^ (y >> 1) ^ mag01[y&0x1UL]; } for (; kk < MT_N - 1; kk++) { y = (mt[kk] & MT_UPPER_MASK) | (mt[kk+1] & MT_LOWER_MASK); mt[kk] = mt[kk+(MT_M-MT_N)] ^ (y >> 1) ^ mag01[y&0x1UL]; } y = (mt[MT_N-1] & MT_UPPER_MASK) | (mt[0] & MT_LOWER_MASK); mt[MT_N-1] = mt[MT_M-1] ^ (y >> 1) ^ mag01[y&0x1UL]; mti = 0; } y = mt[mti++]; y ^= (y >> 11); y ^= (y << 7) & 0x9d2c5680UL; y ^= (y << 15) & 0xefc60000UL; y ^= (y >> 18); return y; } void shuffle_permutation(int N, int p[], int K) { if (N == 1) return 0; int i, j, k; for (k = 0; k < K; k++) { do { i = genrand() % N + 1; j = genrand() % N + 1; } while (i == j); p[i] ^= p[j]; p[j] ^= p[i]; p[i] ^= p[j]; } } void chmax(int* a, int b) { if (*a < b) *a = b; } typedef struct Edge { struct Edge *next; int v; } edge; int main() { init_genrand(46); struct timeval t; double beg, cur; gettimeofday(&t, NULL); beg = t.tv_sec + (double)t.tv_usec / 1000000; int i, j, k = 0, l, N, A[100001], prime[100001], max[100001], flag[1000001] = {}, m[100001], *p[100001], *e[100001]; scanf("%d", &N); for (i = 1; i <= N; i++) { scanf("%d", &(m[i])); p[i] = (int*)malloc(sizeof(int) * (m[i] + 1)); e[i] = (int*)malloc(sizeof(int) * (m[i] + 1)); for (j = 1, A[i] = 1; j <= m[i]; j++) { scanf("%d %d", &(p[i][j]), &(e[i][j])); for (l = 0; l < e[i][j]; l++) A[i] *= p[i][j]; if (flag[p[i][j]] == 0) { prime[++k] = p[i][j]; max[k] = e[i][j]; flag[p[i][j]] = k; } else chmax(&(max[flag[p[i][j]]]), e[i][j]); } } edge *adj[100001] = {}, ed[1000001], *po; for (i = 1, l = 0; i <= N; i++) { for (j = 1; j <= m[i]; j++) { if (e[i][j] != max[flag[p[i][j]]]) continue; ed[l].v = i; ed[l].next = adj[flag[p[i][j]]]; adj[flag[p[i][j]]] = &(ed[l++]); } } int q[100001], live[100001], ans = k + 1, q_ans[100001]; for (i = 1; i <= k; i++) q[i] = i; shuffle_permutation(k, q, k * 10); while (1) { gettimeofday(&t, NULL); cur = t.tv_sec + (double)t.tv_usec / 1000000; if (cur - beg > 3.99) break; for (i = 1; i <= N; i++) live[i] = 1; for (i = 1; i <= k; i++) { j = q[i]; for (po = adj[j], live[0] = 0; po != NULL; po = po->next) { if (live[po->v] == i) { live[po->v]++; live[0] = 1; } } if (live[0] == 0) break; } if (ans > i) { ans = i; for (i = 1; i <= k; i++) q_ans[i] = q[i]; } shuffle_permutation(k, q, 1000 + genrand() % 2); } if (ans == k + 1) { printf("-1\n"); fflush(stdout); return -1; } int num[100001] = {}; printf("%d\n", ans); for (i = 1; i <= N; i++) live[i] = 1; for (i = 1; i <= ans; i++) { j = q[i]; for (po = adj[j]; po != NULL; po = po->next) if (live[po->v] == i) live[po->v]++; } for (i = 1; i <= N; i++) num[live[i]]++; for (i = 1; i <= ans; i++) { printf("%d", num[i]); for (j = 1; j <= N; j++) if (live[j] == i) printf(" %d", A[j]); printf("\n"); } fflush(stdout); return 0; }