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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118 | #include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
#define PII pair<int,int>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
const int mxn = 200005;
PII E[mxn];
int d[mxn];
vector <int> V[mxn];
bool used[mxn];
bool visited[mxn];
vector <int> R;
int dfs(int u){
visited[u] = true;
int result = 1;
for(int i=0; i<V[u].size(); ++i)
if(!used[V[u][i]]){
int x;
if(u == E[V[u][i]].st)
x=E[V[u][i]].nd;
else
x=E[V[u][i]].st;
if(!visited[x])
result+= dfs(x);
}
return result;
}
void DFS(int u){
visited[u] = true;
R.pb(u);
for(int i=0; i<V[u].size(); ++i)
if(!used[V[u][i]]){
int x;
if(u == E[V[u][i]].st)
x=E[V[u][i]].nd;
else
x=E[V[u][i]].st;
if(!visited[x])
DFS(x);
}
}
int main() {
int n, m, D;
scanf("%d %d %d", &n, &m, &D);
for(int i=1; i<=m; ++i){
int a, b;
scanf("%d %d", &a, &b);
V[a].pb(i);
V[b].pb(i);
E[i] = mp(a, b);
d[a]++;
d[b]++;
}
queue <int> Q;
for(int i=1; i<=n; ++i)
if(d[i] < D)
Q.push(i);
while(!Q.empty()){
int k=Q.front();
Q.pop();
for(int i=0; i<V[k].size(); ++i)
if(!used[V[k][i]]){
used[V[k][i]] = true;
int x;
if(k == E[V[k][i]].st)
x=E[V[k][i]].nd;
else
x=E[V[k][i]].st;
d[x]--;
if(d[x] == D-1)
Q.push(x);
}
}
int result = 0;
int best_one = 0;
for(int i=1; i<=n; ++i)
if(d[i] >= D && !visited[i]){
int x = dfs(i);
if(x > result){
result = x;
best_one = i;
}
}
if(result == 0){
puts("NIE");
return 0;
}
for(int i=1; i<=n; ++i)
visited[i] = false;
printf("%d\n", result);
DFS(best_one);
sort(R.begin(), R.end());
for(int i=0; i<result; ++i)
printf("%d ", R[i]);
return 0;
}
|