[백준] 9372번 상근이의 여행 (silver 4

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        int t=Integer.valueOf(br.readLine());
        for(int i=0;i<t; i++){
            StringTokenizer st=new StringTokenizer(br.readLine());
            int n=Integer.valueOf(st.nextToken());
            int m=Integer.valueOf(st.nextToken());

            for(int j=0; j<m;j++){
                st=new StringTokenizer(br.readLine());
            }
            bw.write(n-1+"\n");
        }
        bw.flush();
    }
}


// 모든 국가를 여행하고, 최소의 비행기를 타야한다. 
// 최단경로 x , 모든케이스를 연결하는 신장트리를 구해야한다. 모든 국가를 방문해야하므로.
// 그리고 신장트리는 결국 n개 노드가 있으면, n-1의 경로를 지나야 할 수 밖에 없다.
// 따라서 n-1이 답이다.