Challenge 15: The Longest Road Solution

In trying to be a good dad1, 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 board2. One way to score two points in this game is to build the longest road3. 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.

Programming Challanges
This is based on 539 - Settlers of Catan problem on the UVa Online Judge.

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 mlines 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-fa18-assignments # Go to assignments repository
$ git checkout master # Make sure we are on master
$ git pull --rebase # Pull any changes from GitLab

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

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

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

$ git push -u origin challenge15 # Send changes to GitLab
To check your code, you can use the .scripts/submit.py script or curl:

$ .scripts/submit.py
Submitting challenge15 assignment ...
Submitting challenge15 code ...
Result Success
Score 6.00
Time 0.03

$ curl -F source=@challenge15/program.cpp https://dredd.h4x0r.space/code/cse-30872-fa18/challenge15
{"score": 6, "result": "Success"}
Once you have commited your work and pushed it to GitLab, member to create a merge request. Refer to the Reading 08 TA List to determine your corresponding TA for the merge request.


Work-life balance yo. ↩
And abusing the trade policies, and putting the robber on your land (jerks). ↩
A dangerous race... never works out for me. ↩