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
#include <stdio.h>
#include <string.h>

int main(int argc, char *argv[])
{
    int ii, n, m, d;
    scanf("%d %d %d\n", &n, &m, &d);
    int miasta[n+1], drogia[d], drogib[d];
    memset(miasta, 0, sizeof(miasta));
    for (ii = 0; ii < m; ii ++) {
        int a, b;
        scanf("%d %d", &a, &b);
        miasta[a] ++;
        miasta[b] ++;
        drogia[ii] = a;
        drogib[ii] = b;
    }
    int miasta_ok[n], mok = 0;
    int miasta_be[n], mbe = 0;


    for (ii = 1; ii <= n; ii ++) {
        // zaznaczamy które miasta pasują a które nie
        if (miasta[ii] >= d) {
            miasta_ok[mok] = ii;
            mok++;
        } else {
            miasta_be[mbe] = ii;
            mbe++;
            miasta[ii] = 0;
        }
    }
    for (;;) {
        int a, b, koniec = 1;
        for (ii = 0; ii <m; ) {
            a = drogia[ii];
            b = drogib[ii];
            if (miasta[a] <= 0 && miasta[b] > 0) {
                miasta[b] --;
            } else if (miasta[a] > 0 && miasta[b] <= 0) {
                miasta[a] --;
            }
            if (miasta[a] <= 0 || miasta[b] <= 0) {
                m--;
                if (ii == m)
                    break;
                drogia[ii] = drogia[m];
                drogib[ii] = drogib[m];
            } else {
                ii++;
            }
        }
        for (ii = 0; ii < mok; ) {
            if (miasta[miasta_ok[ii]] < d) {
                // znaczy nie koniec
                koniec = 0;
                miasta[miasta_ok[ii]] = 0;
                mok--;
                if (ii == mok)
                    break;
                miasta_ok[ii] = miasta_ok[mok];
            } else {
                ii ++;
            }
        }
        if (koniec)
            break;
    }
    if (mok == 0) {
        printf("NIE\n");
        return 0;
    }
    printf("%d\n", mok);
    for (ii = 1; ii <= n; ii ++) {
        if (miasta[ii])
            printf("%d ", ii);
    }
    printf("\n");
    
    return 0;
}