We are all familiar with bipartite graph, actually it can be extended to multipartite graph.
If vertices of an undirected graph $G$ can be divided into exactly $k$($k \geq 2$) non-empty sets, and for each pair of vertices $u$ and $v$, there exists an edge ($u$, $v$) if and only if they are from different sets, then $G$ is defined as a complete $k$-partite graph.
Given an undirected graph $G$ with $n$ vertices and $m$ edges, judge whether it is a complete $k$-partite graph.
输入格式
The first line contains an integer number T, the number of test cases.
For each test case :
The first line contains two integers $n$ and $m$($1 \leq n \leq 1000, 0 \leq m \leq \frac{n \times (n - 1)}{2}$), the number of vertices and edges.
i-th of each next m lines contains two integers $u_{i}$ ans $v_{i}$, which means there exists an undirected edge between $u_{i}$ and $v_{i}$ ($1 \leq u_{i}, v_{i} \leq n, u_{i} \neq v_{i}$).
It's also guaranteed that no duplicated edges in the input.
输出格式
For each test case :
print a number $k$ if $G$ is a complete $k$-partite graph($k \geq 2$), print "0"(without quotation) otherwise.
