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
119
120
#include <stdio.h>
#include <stdlib.h>

int n, m, d;

struct node {
  int num;
};

struct list {
  struct list *next;
  struct node *node;
};

struct list_head {
  struct list *list;
  int count;
};

struct node nodes[200000+1];
struct list_head adj[200000+1];

struct list * list_add_front(struct list_head *head, struct node *node)
{
  struct list *newl = malloc(sizeof(*newl));
  struct list *old = head->list;

  newl->next = old ? old : 0;
  newl->node = node;
  head->list = newl;
  head->count++;

  return newl;
}



void delete(int num, struct node *node)
{
  struct list_head *head = &adj[num];
  struct list *e = head->list, *prev;

  for (prev = 0; e; prev = e, e = e->next) {
    if (e->node == node) {
      if (prev) {
	prev->next = e->next;
      } else {
	head->list = e->next;
      }
      head->count -= 1;
      return;
    }
  }
}

int main(int argc, char *argv[])
{
  int i;
  int changed;
  scanf("%d %d %d", &n, &m, &d );

  for (i = 1; i <= n; i++)
    nodes[i].num = i;

  for (i = 0; i < m; i++) {
    int from, to;
    scanf("%d %d", &from, &to);
    list_add_front(&adj[from], &nodes[to]);
    list_add_front(&adj[to], &nodes[from]);
  }

  /*
  for (i = 1; i <= n; i++) {
    if (adj[i].count < d) {
      printf("dropping node %d: adj %d < d %d\n", i, adj[i].count, d);
    }
  }

  */

  do {
    changed = 0;

    for (i = 1; i <= n; i++) {
      if (adj[i].count > 0 && adj[i].count < d) {
	struct list *e1;
	for (e1 = adj[i].list; e1; e1 = e1->next) {
	  delete(e1->node->num, &nodes[i]);
	  changed = 1;
	}
	adj[i].count = 0;
      } 
    }
  } while (changed);

  changed = 0;
  for (i = 1; i <= n; i++) {
    if (adj[i].count >= d) {
      //      printf("%d ", i);
      changed++;
    }
  }

  if (!changed)
    printf("NIE\n");
  else {
    printf("%d\n", changed);
    for (i = 1; i <= n; i++) {
      if (adj[i].count >= d) {
	printf("%d ", i);
      }
    }
    printf("\n");
    
  }
    
  return 0;
}