9372 상근이의 여행

ylab 2023. 3. 24. 23:46

https://www.acmicpc.net/problem/9372

9372번: 상근이의 여행

첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가

www.acmicpc.net

#상근이의 자아 찾기
#가장 적은 종류의 비행기를 타고 모든 국가들을 여행
#상근이가 한 국가에서 다른 국가로 이동할 때 다른 국가를 거쳐가도 된다
#맨처음은 bfs? dfs? 라고 생각했는데 모든 국가가 연결되어있으므로 사실 비행기는 국가-1일 수 밖에 없다.
import sys
input = sys.stdin.readline
t= int(input())
for _ in range(t):
    n,m = map(int,input().split())
    for _ in range(m):
        a,b = map(int,input().split())
    print(n-1)