1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 #include #include #include #include #include #define endl "\n" typedef long long ll; const int MAKS = 200 * 1000; using namespace std; vector neighbours[MAKS]; bool visited[MAKS]; int non[MAKS]; int n, m, d; void decrease(int k){ non[k] = -1; for (int i = 0; i < neighbours[k].size(); i++){ int pom = neighbours[k][i]; if (non[pom] != -1){ non[pom]--; if (non[pom] < d) decrease(pom); } } } void read(){ int a, b; cin >> n >> m >> d; for(int i = 0; i < m; i++){ cin >> a >> b; a--; b--; neighbours[a].push_back(b); neighbours[b].push_back(a); non[a]++; non[b]++; } for (int i = 0; i < n; i++){ if (non[i] > 0 && non[i] < d) decrease(i); } } void solve(){ queue bfs; vector bestanswer; for (int i = 0; i < n; i++){ if (!visited[i] && non[i] >= d){ vectorcurrentanswer; bfs.push(i); while (!bfs.empty()){ int idx = bfs.front(); bfs.pop(); if (!visited[idx]){ visited[idx] = 1; currentanswer.push_back(idx); int sizeoofneighbour = neighbours[idx].size(); for (int j = 0; j < sizeoofneighbour; j++){ int a = neighbours[idx][j]; if (non[a] >= d && !visited[a]) bfs.push(a); } } if (currentanswer.size() > bestanswer.size()) bestanswer = currentanswer; } } } sort(bestanswer.begin(), bestanswer.end()); int pom2 = bestanswer.size(); if (pom2 < 2){ cout << "NIE" << endl; return; } cout << pom2 << endl; for (int i = 0; i < pom2 - 1; i++){ cout << bestanswer[i] + 1 << " "; } cout << bestanswer[pom2 -1] + 1<< endl; } int main() { ios_base::sync_with_stdio(0); read(); solve(); return 0; }