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
142
143
144
145
146
147
148
149
#include <cstdio>
#include <unordered_set>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

struct Node
{
    unordered_set< int > e;
    int i;
    int visited = 0;    
};

int main( int argc, char* argv[] )
{
    int n, m, d;
    
    scanf("%d %d %d", & n, & m, & d );
    
    vector< Node > graph( n );
    
    for( int i = 0; i < n; ++i )
    {
        graph[i].i = i; 
    }
    
    for( int e = 0; e < m; ++e )
    {
        int a, b;
        
        scanf("%d %d", & a, & b );
        
        graph[a - 1].e.insert(b - 1);
        graph[b - 1].e.insert(a - 1);
    }
    
    int curr_visisted = 1;
    
    {
        stack< Node* > S;        
        
        for( int i = 0; i < n; ++i )
        {
            if( graph[i].e.size() < d )
            {
                graph[i].visited = curr_visisted;
                S.push( & graph[i] );
            }
        }
        
        while( ! S.empty() )
        {
            Node* v = S.top();
            S.pop();
            
            for( int e : v->e ) {
                graph[ e ].e.erase( v->i );
                if( graph[ e ].visited != curr_visisted && graph[e].e.size() < d ) {
                    graph[ e ].visited = curr_visisted;
                    S.push( & graph[e] );
                }
            }
            
            v->e.clear();
        }
    }
    
    int most_n = 0;
    int most_v = -1;
    
    curr_visisted = 2;
    
    for( int i = 0; i < n; ++i )
    {
        if( graph[i].visited != curr_visisted && ! graph[i].e.empty() )
        {
            int i_n = 0;
            int i_v = i;
            
            stack< Node* > S2;
            graph[i].visited = curr_visisted;
            S2.push( & graph[i] );
            
            while( ! S2.empty() )
            {
                Node* v = S2.top();
                S2.pop();
                
                ++i_n;
                
                for( int e : v->e ) {
                    if( graph[ e ].visited != curr_visisted ) {
                        graph[ e ].visited = curr_visisted;
                        S2.push( & graph[e] );
                    }
                }
            }
            
            if( i_n > most_n ) 
            {
                most_n = i_n;
                most_v = i_v;
            }
        }
    }
    
    if( most_v == -1 ) 
    {
        printf("NIE\n");
    }
    else
    {
        vector< int > result;
        
        curr_visisted = 3;
        stack< Node* > S3;
        
        graph[ most_v ].visited = curr_visisted;
        S3.push( & graph[ most_v ] );
        
        while( ! S3.empty() )
        {
            Node* v = S3.top();
            S3.pop();
            
            result.push_back( v->i );
            
            for( int e : v->e ) {
                if( graph[ e ].visited != curr_visisted ) {
                    graph[ e ].visited = curr_visisted;
                    S3.push( & graph[e] );
                }
            }
        }
        
        sort( begin(result), end(result) );
        
        printf("%d\n", (int)result.size() );
        for( int i = 0; i < result.size() - 1; ++i )
        {
            printf("%d ", result[i] + 1);
        }
        printf("%d\n", result.back() + 1);
    }
    
    return 0;
}