/* ID: espr1t TASK: KEYWORDS: */ #include #include #include #include #include using namespace std; FILE *in; FILE *out; const int MAX = 1024; int n, k; bool rev[MAX]; int deg[MAX]; bool v[MAX][MAX]; int main(void) { in = fopen("hub.in", "rt"); out = fopen("hub.out", "wt"); fscanf(in, "%d %d", &n, &k); for (int i = 0; i < n * (n - 1) / 2; i++) { int node1, node2; fscanf(in, "%d %d", &node1, &node2); v[node1][node2] = true; deg[node1]++; } for (int i = 0; i < k; i++) { memset(rev, 0, sizeof(rev)); int p; fscanf(in, "%d", &p); for (int c = 0; c < p; c++) { int node; fscanf(in, "%d", &node); rev[node] = true; } vector rr, nr; for (int node = 0; node < n; node++) { if (rev[node]) rr.push_back(node); else nr.push_back(node); } for (int i1 = 0; i1 < (int)rr.size(); i1++) { int node1 = rr[i1]; for (int i2 = 0; i2 < (int)nr.size(); i2++) { int node2 = nr[i2]; deg[node1] += v[node1][node2] ? -1 : +1; deg[node2] += v[node2][node1] ? -1 : +1; v[node1][node2] = !v[node1][node2]; v[node2][node1] = !v[node2][node1]; } } int hub = -1; for (int node = 0; node < n; node++) { if (deg[node] == n - 1) { hub = node; break; } } fprintf(out, "%d\n", hub); } return 0; }