• 뭔가 이상한 느낌이 들면 정상이다. 사실상 함정문제.
• N개의 노드를 전부 연결하려면 최소 N-1개의 엣지가 필요하다. 최소 갯수만 출력하면 되므로, 어떤 엣지가 필요한지는 생각할 필요가 없다. 그냥 입력받은 N값에서 -1만 해서 출력하면 된다. 그래서 계산시간은 케이스당 O(1)이지만.. 다음 테스트케이스로 넘어가려면 M줄의 입력을 받아야 하긴 하므로 입력시간까지 고려하면 O(M)이 된다..

"""Solution code for "BOJ 9372. 상근이의 여행".

- Problem link: https://www.acmicpc.net/problem/9372
- Solution link: http://www.teferi.net/ps/problems/boj/9372
"""

import sys


def main():
    T = int(sys.stdin.readline())
    for _ in range(T):
        N, M = [int(x) for x in sys.stdin.readline().split()]
        for _ in range(M):
            flight = sys.stdin.readline()  # pylint: disable=unused-variable

        print(N - 1)


if __name__ == '__main__':
    main()