UVa 539

539 The Settlers of Catan

• http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=480

Summary

Find the longest trail in a graph (ie: no repeated edges, possibly repeated vertices)

Explanation

This is a simple problem with a brute-force solution. There are only up to 25 nodes with up to 25 edges, so a brute-force approach will work fine.

For each vertex, perform a Depth-First Search on the graph. Find the longest trail you can traverse in this manner.

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

2
12