Challenge 15: The Longest Road

In trying to be a good dad¹, the instructor has started playing board games with his kids. Besides classics like Candy Land, they have been playing newer games such as Catan Junior in hopes of graduating to more sophisticated games such as Settlers of Catan.

In Settlers of Catan, players attempt to dominate an island by building roads, settlements, and cities across the whole board². One way to score two points in this game is to build the longest road³. Unfortunately, for young players determining the longest road can be difficult since the road network can be quite complex as shown below.

Your job is to help Abigail, Madeline, and Caleb (the instructor's children) by writing a program that determines the longest road on the game board. To simplify the problem, we will just consider computing the longest road for a single player:

• You are given a set of nodes (cities)

• You are given a set of edges (road segments) of length 1 connecting the nodes

• The longest road is defined as the longest path within the network that doesn't use an edge twice. Nodes may be visited more than once, however.

For example:

o      o--o      o
 \    /    \    /
  o--o      o--o
 /    \    /    \
o      o--o      o--o
           \    /
            o--o

In the network above, the longest road is length 12.

Input¶

The input will contain multiple test cases. The first line of each test case contains two integers: the number of nodes n (2 <= n <= 25) and the number of edges m (1 <= m <= 25). The next m lines describe the undirected edges, where each edge is given by the numbers of the two nodes connected by it. The nodes are labeled from 0 to n - 1 and have degress of three or less. The network itself is not necessarily connected.

The input will be terminated by two values of 0 for n and m.

Example Input¶

3 2
0 1
1 2
15 16
0 2
1 2
2 3
3 4
3 5
4 6
5 7
6 8
7 8
7 9
8 10
9 11
10 12
11 12
10 13
12 14
0 0

Output¶

For each test case, output the length of the longest road.

Example Output¶

2
12

Submission¶

To submit your work, follow the same procedure you used for Reading 00:

$ cd path/to/cse-30872-fa24-assignments     # Go to assignments repository
$ git checkout master                       # Make sure we are on master
$ git pull --rebase                         # Pull any changes from GitHub

$ git checkout -b challenge15               # Create and checkout challenge15 branch

$ $EDITOR challenge15/program.py            # Edit your code

$ git add challenge15/program.py            # Stage your changes
$ git commit -m "challenge15: done"         # Commit your changes

$ git push -u origin challenge15            # Send changes to GitHub

To check your code, you can use the .scripts/check.py script or curl:

$ .scripts/check.py
Checking challenge15 program.py ...
  Result Success
    Time 0.03
   Score 6.00 / 6.00

$ curl -F source=@challenge15/program.py https://dredd.h4x0r.space/code/cse-30872-fa24/challenge15
{"result": "Success", "score": 6, "time": 0.03198695182800293, "value": 6, "status": 0}