[uva] 11080 – place the guards

from collections import deque


def ():
    T = int(input())
    for t in range(T):
        v, e = map(int, input().split())
        g = [[0] * v for _ in range(v)]
        for i in range(e):
            a, b = map(int, input().split())
            if not g[a][b]:
                g[a][b] = 1
                g[b][a] = 1
        color = [-1] * v
        check = True
        ans = 0
        for idx, item in enumerate(color):
            if not check:
                break
            if item == -1:
                q = deque()
                q.append(idx)
                color[idx] = 0
                cnt = [1, 0]
                while q and check:
                    tmp = q.popleft()
                    for i in range(v):
                        if g[tmp][i]:
                            if color[i] == -1:
                                q.append(i)
                                color[i] = 1 - color[tmp]
                                cnt[1 - color[tmp]] += 1
                            elif color[i] == color[tmp]:
                                check = False
                                break
                ans += max(1, min(cnt))
        if check:
            print(ans)
        else:
            print(-1)


if __name__ == "__main__":
    main()