e-olymp
Problems

Clique

Clique

Cliquein an undirected graphis a subsetof vertices,two of whichare connectedby an edgeof the graph.In other words,it is a completesubgraphof the originalgraph.Cliquesizeis defined as thenumber of verticesin it.Your task- to determine thesize of the largestcliquein the graph.

Input

The firstline containsa single number -the number of testsT. This is followed bydescriptions ofTtests.Eachtest descriptionbeginswith the lineon which thetwo integersN (1N20) and M (0MN(N-1)/2), where:

  • Nnumberof vertices,
  • Mnumber of edges.

This is followed byM lines, ithlinecontains a pairof numbers (si, fi) – numberof verticesbetween whichthere is an edge (1si, fiN). All pairs (si, fi) are different,one edgemay not bein the input datatwice.In thegraph has nomultiple edges(connectinganypair of verticesis at most oneedge).In thegraph has noelementarycycle(for each pair (si, fi) is true, thatsifi).

Output

For each of theTtestoutputon a linesingle number - thesize of the largestcliqueof the graph.

Time limit 25 seconds
Memory limit 64 MiB
Input example #1
3
2 0
2 1
1 2
3 2
1 2
2 3
Output example #1
1
2
2