Maximum Compatible Pairs in Circular Seating

You are given a set of guests and a list of pairwise relationships indicating which two guests enjoy each other’s company. Your task is to arrange the guests around a circular table in such a way that the number of adjacent pairs (neighbors around the table) who are compatible is maximized.

Formally, you are given an integer \(N\) denoting the number of guests and an integer \(M\) denoting the number of pair relationships. Then, \(M\) lines follow, each containing two integers \(A\) and \(B\) representing that guest \(A\) and guest \(B\) are compatible. As the table is circular, guest 1 is considered adjacent to guest 2, guest 2 to guest 3, …, and guest \(N\) is adjacent to guest 1.

Determine the maximum number of adjacent compatible pairs that can be achieved by seating the guests in an optimal order.

inputFormat

The input is read from stdin and has the following format:

T
N M
A1 B1
A2 B2
... (M lines)
... (Next test case if any)

</p>

Where:

• T is the number of test cases.
• For each test case, the first line contains two integers: N (the number of guests) and M (the number of compatible pairs).
• The next M lines each contain two integers \(A\) and \(B\) indicating that guest A and guest B are compatible.
• Constraints are small enough to allow checking all permutations.

outputFormat

For each test case, output a single integer on a new line representing the maximum number of adjacent compatible pairs achievable in an optimal seating arrangement. The output should be written to stdout.

## sample

1
4 4
1 2
2 3
3 4
4 1

4