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
150
151
// mis.cpp : Defines the entry point for the console application.
//


#include "stdio.h"

#define	MM		200000L			// max. liczba miast
#define	DD		200000L			// max. liczba dróg


struct	ddd	{
				long	 ma;
				long	 mb;
			} ;

struct	mmm	{
				long	 z;		// numer zbioru do którego należy (-1 - nie należy, 0 - nierozpoznany, >0 - zbiór)
				long	 d;		// bieżąca liczba dróg w czasie wczytywania danych/przetwarzania
				long	 n;		// liczba dróg wychodzących
				long	*pp;
			} ;


struct	 mmm	 mm[MM];		// miasta
struct	 ddd	 dd[DD];		// drogi;
long			 pp[DD+DD];		// przetworzone końcówki połączeń

long			 ss[MM];		// stos

long			 m;				// liczna miast
long			 d;				// liczba dróg
long			 k;				// parametr

long			 z;				// bieżący numer zbioru
long			 zMax;			// liczba miast w bieżącym zbiorze

long			 w;				// numer zbioru z największą liczbą miast
long			 wMax;			// liczba miast w zbiorze z największą liczbą miast


int main()
{
	long		 i, j, ma, mb, n, p, s;

	scanf("%ld %ld %ld", &m, &d, &k);
	for (i=0; i<d; i++)
	{
		scanf("%ld %ld", &ma, &mb);
		ma--;
		mb--;
		dd[i].ma	= ma;
		dd[i].mb	= mb;
		mm[ma].n++;
		mm[mb].n++;
	}

	p	= 0;
	for (i=0; i<m; i ++)
	{
		mm[i].pp	= &pp[p];
		p	+= mm[i].n;
	}

	for (i=0; i<d; i++)
	{
		ma	= dd[i].ma;
		mb	= dd[i].mb;
		mm[ma].pp[mm[ma].d++]	= mb;
		mm[mb].pp[mm[mb].d++]	= ma;
	}

	s	= 0;
	for (i=0; i<m; i++)
	{
		if (mm[i].d<k)
		{
			mm[i].z	=-1;
			ss[s++]	= i;
		}
	}

	while (s>0)
	{
		ma	= ss[--s];
		n	= mm[ma].n;

		for (j=0; j<n; j++)
		{
			mb	= mm[ma].pp[j];
			d	= --mm[mb].d;
			if (mm[mb].z==0 && d<k)
			{
				mm[mb].z	= -1;
				ss[s++]		= mb;
			}
		}
	}

	for (i=0; i<m; i++)
	{
		if (mm[i].z==0)
		{
			mm[i].z	= ++z;
			zMax	= 0;
			s		= 0;
			ss[s++]	= i;
			while (s>0)
			{
				zMax++;

				ma	= ss[--s];
				n	= mm[ma].n;

				for (j=0; j<n; j++)
				{
					mb	= mm[ma].pp[j];
					if (mm[mb].z==0)
					{
						mm[mb].z	= z;
						ss[s++]		= mb;
					}
				}
			}

			if (zMax>wMax)
			{
				w		= z;
				wMax	= zMax;
			}
		}
	}

	if (w>0)
	{
		printf("%ld\n", wMax);
		for (i=0; i<m; i++)
		{
			if (mm[i].z==w)
			{
				printf("%ld ", i+1);
			}
		}
		printf("\n");
	}
	else
	{
		printf("NIE\n");
	}

	return 0;
}