407012: GYM102680 G Bike Race

David, Daniel, and Billy, captains of the Doofenshmirtz biker-gang, decide to have an irresponsibly destructive race across the tri-state area that contains $$$n$$$ intersections and $$$m$$$ bidirectional roads. In the interest of having their unmuffled engines create the optimal amount of chaos, they want their race to pass through as many intersections as possible. However, since all three racers are logically infallible and bike optimally, they know that everyone will race to the finish passing through the fewest intersections necessary. The racers agree that the race should both start and end at an intersection.

Can you help them find the length of the race that will pass through the greatest number of the $$$n$$$ intersections in the tri-state area, if all three racers pass through the fewest intersections necessary?

It is guaranteed that all intersections will be directly or indirectly reachable from all others.

The line contains a single integer $$$T$$$, the number of test cases.

The first line of each test cases contains two integers $$$n$$$, the number of intersections, and $$$m$$$, the number of roads

$$$m$$$ lines follow, each containing two integers representing two intersections connected by a road. Intersections are 1-indexed (they are numbered 1, 2, 3, ... $$$n$$$). So "1 3" would mean that a road connects intersection 1 and intersection 3. A road may start and end at the same city, and two different roads may connect the same two cities.

$$$1 \leq T \leq 100$$$

$$$1 \leq n \leq 500$$$

$$$1 \leq m \leq 1000$$$

The sum of $$$n$$$ over all testcases will not exceed 1000.

Output T lines, with each containing a single integer representing the length of the longest possible race.

2
3 3
1 2
3 1
2 3
5 4
1 2
3 2
3 4
5 4

1
4

There are two samples. The first consists of 3 intersections and 3 roads, with each intersection directly connected to each other intersection. If any two cities are picked as starting and ending locations, the racers will take a path that passes only through those two cities.

For the second test case, there are 5 cities, with each one connected to the two ones with adjacent numerical representations. The longest race possible would start at intersection 0 and end at intersection 4, passing through all 5 intersections.