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
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<set>
#include<assert.h>
using namespace std;
#define FOR(i,a,b) for(int i = a; i <= b; ++i)
#define FORD(i,a,b) for(int i = a; i >= b; --i)
#define REP(i,n) FOR(i,0,(n)-1)
#define RI(i,n) FOR(i,1,n)
#define pb push_back
#define mp make_pair
#define st first
#define nd second
#define mini(a,b) a=min(a,b)
#define maxi(a,b) a=max(a,b)
bool debug;
typedef vector<int> vi;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int inf = 1e9 + 5;
const int nax = 2e5 + 5;

int n,m,d,a,b;
vi dowora, dupa, pom;
vector<pii> v[nax];
bool ni_ma_w[nax];
int st[nax];

void dfs(int x) {
  ni_ma_w[x] = true;
  pom.pb(x);
  for (auto w: v[x]) {
    if (!ni_ma_w[w.st]) {
      dfs(w.st);
    }
  }
}

int main(int argc, char * argv[]) {
	debug = argc > 1;
  scanf("%d%d%d",&n,&m,&d);
  REP(i,m) {
    scanf("%d%d",&a,&b);
    v[a].pb(mp(b,i));
    v[b].pb(mp(a,i));
  }
  
  FOR(i,1,n) st[i] = v[i].size();
  FOR(i,1,n) if (st[i] < d) {
    ni_ma_w[i] = true;
    dowora.pb(i);
  }
  
  while (!dowora.empty()) {
    int x = dowora.back();
    dowora.pop_back();
    
    for (auto p: v[x]) if (!ni_ma_w[p.st]) {
      --st[p.st];
      if (st[p.st] < d) {
        ni_ma_w[p.st] = true;
        dowora.pb(p.st);
      }
    }
  }
  
  FOR(i,1,n) if (!ni_ma_w[i]) {
    pom.clear();
    dfs(i);
    if (pom.size() > dupa.size()) dupa = pom;
  }
  
  sort(dupa.begin(), dupa.end());
  if (dupa.empty()) {
    puts("NIE");
  } else {
    printf("%d\n",(int)dupa.size());
    for (auto x: dupa) {
      printf("%d ",x);
    }
    puts("");
  }
	return 0;
}