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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include <vector>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <fstream>
#include <stdio.h>

typedef std::vector< long int > VI;
typedef std::vector< bool > VB;
typedef std::vector< VB > MB; 

int main( int argc, char* argv[] )
{
    long int n;
    long int m;; 
    long int d; 
    std::cin >> n >> m >> d;
    MB MIASTA;
    VB v0(n+1,false);
    VB ret(n+1, false);
    for( int i=0; i<=n; ++i )
        MIASTA.push_back( v0 );

    VB wolne( n+1, false ); 
    for( int i=0; i<m; ++i )
    {
        long int x, y; 
        //file >> x >> y;
//        std::cin >> x >> y;
        scanf("%ld",&x);
        scanf("%ld",&y);
        MIASTA[x][y] = true;
        MIASTA[y][x] = true;
        wolne[x] = true;
        wolne[y] = true;
    }
          
    bool changed = true;
    while( changed )
    {
        changed = false;
        for( int i=1; i<=n; ++i )
            if( std::accumulate( MIASTA[i].begin(), MIASTA[i].end(), 0) < d )
            {
                wolne[i] = false;
                MIASTA[i] = v0; 
                for( int j=1; j<=n; ++j )
                    if( MIASTA[j][i] )
                    {
                        changed = true;
                        MIASTA[j][i] = false;
                    }
            }
    }

    for( long int miasto=1; miasto<=n; ++miasto )
    {
        if( wolne[miasto] == 1 )
        {
            VB tempWolne = wolne; 
            VB tempSet( n+1, 0 );
            tempSet[miasto]=true;
            tempWolne[miasto] = false;
            VI kolejka = { miasto }; 
            long int i;

            while( !kolejka.empty() )
            {
                uint64_t tempMiasto = kolejka.back(); 
                kolejka.pop_back();
                i = 1;
                while( i <= n )
                {
                    if( ( MIASTA[tempMiasto][i] ) && tempWolne[i] )
                    {
                        tempSet[i]= true;
                        tempWolne[i] = 0;
                        kolejka.push_back( i );        
                    }
                    ++i;
                }   
            }
            i = 1;

            bool zmiana = true;
            while( zmiana )
            {
                zmiana = false;
                long int t = 1;
                while( t <= n )
                {
                    if( tempSet[t] == true )
                    {
                        long int current = 0; 
                        for( long int p = 1; p<=n; ++p )
                            if( tempSet[p] & MIASTA[t][p] )
                                ++current;
                        if( current < d )
                        {
                            zmiana = true;
                            tempSet[t]= false;
                        }
                    }
                    ++t;
                }
            }// end while( zmiana )
        
            
            wolne[miasto] = false;
            for( long int p=1; p<=n; ++p )
                if( tempSet[p] == true )
                    wolne[p] = false;
            for( i=1; i <= n; ++i  )
            {
                if( tempSet[i] == true );
                    for( long int p = 1; p<n; ++p )
                        if( MIASTA[i][p] )
                            wolne[i] = false;
            }
            if( std::accumulate(tempSet.begin(), tempSet.end(), 0 ) > std::accumulate( ret.begin(), ret.end(), 0 ) )
                ret = tempSet;
        }
    }

    if( std::accumulate(ret.begin(), ret.end(), 0) > 0 )
    {
        std::cout << std::accumulate(ret.begin(), ret.end(), 0 ) << std::endl;
        long int in = 1;
        while( in <= n )
        {
            if( ret[in] )
                std::cout << in << " ";
            
            ++in;
        }
    }
    else
        std::cout << "NIE";
    std::cout << std::endl;
    return 0;
}