Cycles of Lanes

Each of the $M$ lanes of the park of the Polytechnic University of Bucharest connects two of the park's $N$ crossroads (labeled from $1$ to $N$). No pair of crossroads is connected by more than one lane, and it is possible to travel from any crossroad to any other along a path of one or more lanes. A cycle of lanes is simple when it passes through each of its crossroads exactly once.

The university administration wants to hang, on the lanes, pictures of the winners of the Regional Collegiate Programming Contest, so that the winners from one university appear on the lanes of a single simple cycle. It therefore wants to assign the longest simple cycles to the most successful universities, so the task is to find the longest cycle. Conveniently, each lane of the park belongs to at most one simple cycle (see the figure).

The first line contains the number $T$ of test cases. Each test case starts with a line containing two positive integers $N$ and $M$ separated by a space ($4 \le N \le 4444$): the number of crossroads and the number of lanes. Each of the next $M$ lines contains the labels of the two crossroads joined by one lane.

For each test case, print on a single line the length of a longest simple cycle, where the length is the number of lanes (equivalently, of crossroads) that the cycle contains.