그래프의 욱신함

문제

algospot.com 본부에서 Toivoa "the chairman"이 Astein "the slave"에게 새로운 그래프 문제를 오랫동안 졸라 왔다. 그래서 Astein이 다음 문제를 냈다.

무방향 그래프 $G(V, E)$의 욱신함(Wooksin-ness)은 그래프에 사이클이 생기도록 추가해야 하는 간선의 최소 개수이다. 형식으로 쓰면 다음과 같다.

$\min |E' - E| \quad \text{s.t.} \quad E' \supseteq E \text{ 이고 } G'(V, E') \text{에는 사이클이 하나 이상 있다}$

단, 루프(시작점과 끝점이 같은 간선)와 같은 두 정점 사이의 중복 간선은 허용되지 않는다.

주어진 그래프의 욱신함을 계산하는 프로그램을 작성하라.

입력

입력은 $T$개의 테스트 케이스로 이루어진다. 첫 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 두 정수 $V$와 $E$가 주어진다($1 \le V \le 100$, $0 \le E \le 1000$). $V$는 정점의 개수이고 $E$는 간선의 개수이다. 정점은 0부터 $V - 1$까지 번호가 매겨져 있다. 이어지는 $E$개의 줄에는 간선으로 연결된 두 정점의 번호가 각각 주어진다.

입력에는 루프가 없다. 두 정점 사이의 간선은 최대 하나이다.

출력

각 테스트 케이스마다 한 줄에, 그래프에 사이클이 생기도록 추가해야 하는 간선의 최소 개수를 출력한다. 불가능하면 $-1$을 출력한다.