1. 

package backtracking.settlersOfCatan;
/**
* FWP, Ausgew├¤hlte Probleme aus dem ACM Programming Contest, WS10/11
* Problem: 539 Settlers of Catan
* Link: http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=480
*
* @author Patrick B├ędat
* @version 1.0, 19.12.2010
*
* Method : DP/Backtracking
* Status : Accepted
* Runtime: 0.488
*/
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main
{

static HashMap<Integer, HashSet<Integer>> edges;
static int maxPath = 0;

public static void main(String... args) throws Exception
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

while (true)
{
int nNodes = 0;
int nEdges = 0;
StringTokenizer st = null;

st = new StringTokenizer(reader.readLine());
nNodes = Integer.parseInt(st.nextToken());
nEdges = Integer.parseInt(st.nextToken());

if (nNodes == 0 && nEdges == 0)
break;

edges = new HashMap<Integer, HashSet<Integer>>();

for (int i = 0; i < nEdges; i++)
{
st = new StringTokenizer(reader.readLine());

int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());

HashSet<Integer> neighbours = null;

if (edges.containsKey(from))
neighbours = edges.get(from);
else
{
neighbours = new HashSet<Integer>();
edges.put(from, neighbours);
}

neighbours.add(to);

if (edges.containsKey(to))
neighbours = edges.get(to);
else
{
neighbours = new HashSet<Integer>();
edges.put(to, neighbours);
}

neighbours.add(from);
}

ArrayList<Integer> path = new ArrayList<Integer>();

maxPath = 1;

for (int i = 0; i < nNodes; i++)
{
path.add(i);
findPath(i, 1, path);
path.clear();
}

System.out.println(maxPath - 1);
}
}

static void findPath(int currentNode, int pathLength, ArrayList<Integer> path)
{
maxPath = Math.max(pathLength, maxPath);

int currentIndex = path.indexOf(currentNode);
//traversed twice
if (path.get(0) != currentNode && currentIndex != pathLength - 1)
return;

//node not connected
if (!edges.containsKey(currentNode))
return;

for (Integer neighbour : edges.get(currentNode))
{
int neighbourIndex = path.indexOf(neighbour);

if(neighbourIndex > 0 && neighbourIndex < pathLength && path.get(neighbourIndex - 1) == currentNode)
continue;

if (pathLength > 1 && path.get(pathLength - 2) == neighbour)
continue;

if (path.size() > pathLength)
path.set(pathLength, neighbour);
else
path.add(neighbour);

findPath(neighbour, pathLength + 1, path);
}
}
}