Explosive Materials

Erik is sending samples of $n$ kinds of material to his laboratory for a purity analysis. The kinds are numbered 1 to $n$. He packs the samples into boxes of equal capacity. A box has capacity $c$ if it holds up to $c$ kinds of material.

Some materials react and explode, so they cannot go in the same box. Erik found that if putting $k$ kinds $a_1, \dots, a_k$ in one box explodes, then putting any two of them in one box explodes as well. He wrote down every pair that explodes, and the list has $m$ pairs.

Because every explosion comes from a pair, Erik wants to know whether two boxes of equal capacity are enough. All $n$ kinds must be split between the two boxes, and no two materials in the same box may form a pair from the list. If that is possible, what is the smallest capacity of a box?

The first line contains the number of test cases $T$ ($T \le 20$).

The first line of each test case contains two integers $n$ and $m$ ($1 \le n \le 1000$, $0 \le m \le \min(n(n-1)/2,\ 105432)$), the number of kinds of material and the number of pairs on the list. Each of the next $m$ lines contains two integers $a$ and $b$ ($1 \le a, b \le n$, $a \ne b$), meaning that material $a$ and material $b$ explode when they are put in the same box. No pair is listed twice.

For each test case, print one integer on its own line. Print -1 if the materials cannot be sent in two boxes. Otherwise print the smallest capacity of a box.