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);
        }
    }
}