eolymp
bolt
Try our new interface for solving problems
Problems

Clique

Clique

Time limit 25 seconds
Memory limit 64 MiB

Clique in an undirected graph is a subset of vertices, two of which are connected by an edge of the graph. In other words, it is a complete subgraph of the original graph. Clique size is defined as the number of vertices in it. Your task - to determine the size of the largest clique in the graph.

Input data

The first line contains a single number - the number of tests T. This is followed by descriptions of T tests. Each test description begins with the line on which the two integers N (1N20) and M (0MN(N-1)/2), where:

  • N – number of vertices,

  • M – number of edges.

This is followed by M lines, i^th line contains a pair of numbers (s_i, f_i) – number of vertices between which there is an edge (1s_i, f_iN). All pairs (s_i, f_i) are different, one edge may not be in the input data twice. In the graph has no multiple edges (connecting any pair of vertices is at most one edge). In the graph has no elementary cycle (for each pair (s_i, f_i) is true, that s_if_i).

Output data

For each of the T test output on a line single number - the size of the largest clique of the graph.

Examples

Input example #1
3
2 0
2 1
1 2
3 2
1 2
2 3
Output example #1
1
2
2