폭발성 물질

에릭은 순도 분석을 위해 물질 $n$종의 표본을 실험실로 보내려 한다. 물질에는 1번부터 $n$번까지 번호가 붙어 있다. 표본은 용량이 같은 상자 여러 개에 나누어 담는다. 상자 하나가 물질 $c$종까지 담을 수 있으면 그 상자의 용량은 $c$다.

어떤 물질끼리는 화학 반응으로 폭발을 일으켜서 같은 상자에 담을 수 없다. 에릭은 물질 $k$종 $a_1, \dots, a_k$를 한 상자에 담아 폭발이 일어난다면 그중 두 종만 담아도 폭발이 일어난다는 사실을 알아냈다. 그래서 폭발을 일으키는 물질 쌍을 빠짐없이 적어 쌍 $m$개짜리 목록을 만들었다.

폭발은 모두 물질 두 종 사이에서 일어나므로, 에릭은 용량이 같은 상자 두 개만으로 물질을 안전하게 보낼 수 있는지 궁금하다. 물질 $n$종을 남김없이 두 상자에 나누어 담아야 하고, 한 상자에 든 두 물질이 목록에 있는 쌍이면 안 된다. 보낼 수 있다면 상자 용량의 최솟값은 얼마인가?

첫 줄에 테스트 케이스의 개수 $T$가 주어진다 ($T \le 20$).

각 테스트 케이스의 첫 줄에는 정수 $n$과 $m$이 주어진다 ($1 \le n \le 1000$, $0 \le m \le \min(n(n-1)/2,\ 105432)$). $n$은 물질의 종류 수, $m$은 목록에 있는 쌍의 개수다. 이어지는 $m$개 줄에는 각각 정수 $a$와 $b$가 주어진다 ($1 \le a, b \le n$, $a \ne b$). 물질 $a$와 물질 $b$를 같은 상자에 담으면 폭발이 일어난다는 뜻이다. 같은 쌍이 두 번 주어지지는 않는다.

각 테스트 케이스마다 정수 하나를 한 줄에 출력한다. 상자 두 개로 물질을 보낼 수 없으면 -1을 출력하고, 보낼 수 있으면 상자 용량의 최솟값을 출력한다.