539

Theory:

This is an np-hard problem. As the degree of each node can be at most 3 so using dfs ,it can be solved.

Follow the link

#include <iostream>
#include <stdio.h>
#include <vector>
#include <string.h>

using namespace std;

//vector<int> vb[30];
int mat[30][30];
int visit[30];
int n,m;
int length;

void search(int a,int len)
{
	if(len>length)
		length = len;
	for(int i=0;i<n;i++)
	{
		//a=vb[step][i];
		if(mat[a][i]>0)
		{
			mat[a][i]-=1;
			mat[i][a]-=1;
			search(i,len+1);
			mat[a][i]++;
			mat[i][a]++;
		}

	}
}


int main()
{
	int a,b;
	//memset(visit,0,sizeof(visit));
	while(cin>>n>>m)
	{
		if(n==0 && m==0)
		break;

		memset(mat,0,sizeof(mat));
		//for(int i=0;i<n;i++)
		//vb[i].clear();
		length=0;
		for(int i=0;i<m;i++)
		{
			cin>>a>>b;
			//vb[a].push_back(b);
			//vb[b].push_back(a);
			mat[a][b]++;
			mat[b][a]++;
		}

		int len =0;

		for(int i=0;i<n;i++)
		{
			//visit[0]=1;
			search(i,0);
			//visit[0]=0;
		}

		cout<<length<<"\n";
	}
	return 0;
}