405359: GYM101915 D Largest Group

One day your university decided to run some statistics. They wanted to study friendship relations among boys and girls, and its effectiveness on their grades.

Strange thing about your university is that it has the exact same number of boys and girls. More formally, the university has P boys numbered from 1 to P, and P girls numbered from 1 to P.

We know that any pair of boys are surely friends, and any pair of girls are definitely friends. However, boys and girls are not always friends. To be precise, the university has a list of length N containing the friendship relations between girls and boys. the i^th friendship relation is described by two integers b_i and g_i meaning that the boy number b_i and girl number g_i are friends.

One of the statistics your university is interested in, is the largest group of people (boys and girls) where any pair of them are friends. Can you write a program that would solve such a problem?

The first line contains an integer T, the number of test cases.

Each test case starts with a line containing 2 space separated integers P and N denoting both the number of boys and girls at your university, and the number of friendship relations. (1 ≤ P ≤ 20), (0 ≤ N ≤ P²).

N lines follow. The i^th line of them contains 2 space separated integers b_i, g_i describing a friendship relation.

For each test case print a single line, containing a single integer, denoting the number of people in the largest group where any pair of people among them are friends.

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

5
4