Miscellany

#include <stdio.h>

#define NOTVISITED -1
#define WHITEORBLACK 1
#define WHITE 2
#define BLACK 3


int* col;
bool** mat;
int n;
int* color;
int count = 0;

int* blacknodes;
int limit = 0;
int tempans = 0;
int* ansnodes;
int anslimit = 0;


void DFS(int v,int color,int n)
{
	if(col[v] != NOTVISITED)
		return;
	col[v] = color;
	int i = 0;
	for(i = 0;i < n;i++)
		if(mat[v][i] == true)
			DFS(i,color,n);
}

int max(int x,int y)
{
	return x > y ? x : y;
}


void splitComponents(int n)
{
	int i = 0;
	col = new int[n];
	for(i = 0;i < n;i++)	col[i] = NOTVISITED;
	for(i = 0;i < n;i++)
		if(col[i] == NOTVISITED)
			DFS(i,count,n),count++;
}


int colorGraph(int ver,int curans)
{
	int white = 0,black = 0;
	int i = 0,canBeBlack,justupdate;

	if(tempans < curans)
	{
		tempans = curans;
		limit = 0;
		for(i = 0;i < n;i++)
			if(color[i] == BLACK)
				blacknodes[limit++] = i;
	}
	if(color[ver] == BLACK || color[ver] == WHITE)
		return 0;
	if(color[ver] == WHITEORBLACK)
	{
		//color vertex with white
		color[ver] = WHITE;
		for(i = 0;i < n;i++)
			if(mat[ver][i] == true)
				white = max(white,colorGraph(i,curans));
		//color vertex with black

		canBeBlack = 1;
		for(i = 0;i < n;i++)
			if(i != ver && mat[ver][i] == true && color[i] == BLACK)
			{
				canBeBlack = 0;
				break;
			}
		if(canBeBlack)
		{
			color[ver] = BLACK;
			justupdate = 1;
			for(i = 0;i < n;i++)
				if(mat[ver][i] == true)
				{
					black = max(black,colorGraph(i,1 + curans));
					justupdate = 0;
				}
			if(justupdate)
				colorGraph(ver,1 + curans);
			black++;
		}
		color[ver] = WHITEORBLACK;
	}
	return max(white,black);
}


int findans(int n)
{
	int ans = 0,i = 0,j = 0,k = 0;
	splitComponents(n);
	color = new int[n];
	blacknodes = new int[n];
	ansnodes = new int[n];
	for(i = 0;i < n;i++)	color[i] = WHITEORBLACK;
	for(i = 0;i < count;i++)
		for(j = 0;j < n;j++)
		{
			if(col[j] == i)
			{
				tempans = limit = 0;
				ans += colorGraph(j,0);
				for(k = 0;k < limit;k++)
					ansnodes[anslimit++] = blacknodes[k];
				break;
			}
		}
	return ans;

}

int main()
{
	
	int e;
	int i,j;
	int x,y;

	scanf("%d %d",&n,&e);
	mat = new bool*[n];

	for(i = 0;i < n;i++)
		mat[i] = new bool[n];

	for(i = 0;i < n;i++)
		for(j = 0;j < n;j++)
			mat[i][j] = false;

	for(i = 0;i < e;i++)
	{
		scanf("%d %d",&x,&y);
		x--;
		y--;
		mat[x][y] = mat[y][x] = true;
	}

	int ans;
	ans = findans(n);
	printf("%d\n",ans);
	for(i = 0;i < anslimit-1;i++)
		printf("%d ",ansnodes[i] + 1);
	printf("%d",ansnodes[i]+1);	
	return 0;

}