#include <iostream>

#define MAX_VERTEX 1000

class Graph
{
private:
    int n;
    int graph[MAX_VERTEX][MAX_VERTEX];
    int queue[MAX_VERTEX], visitors[MAX_VERTEX];
    
public:
    void onVisitors(int i) {
        visitors[i] = 1;
    }

    int visit_yet() {
        for(int i = 0; i<n; i++) {
            if(!visitors[i])
                return 0;
        }
        
        return 1;
    }
    
    int BFS(int v) {
        int front = 0, rear = 0;
        int noc = 0;
        bool noc_f;
        
        visitors[v] = 1;
        queue[rear++] = v;
        while(front < rear) {
            
            v = queue[front++];
            noc_f = false;
            for(int i = 0; i<n; i++) {
                
                if(graph[v][i] == 1 && !visitors[i]) {
                    visitors[i] = 1;
                    queue[rear++] = i;
                    
                    noc_f = true;
                }
            }
            
            if(noc_f) noc++;
        }
        
        return noc;
    }
    
    
    void initGraph(int N) {
        n = N;
        
        for(int i=0; i<n; i++) {
            
            visitors[i] = 0;
            
            for(int j=0; j<n; j++) {
                    graph[i][j] = 0;
            }
        }
    }
    
    int EdgeSum(int iter) {
        int sum = 0;
        
        for(int i=0; i<n; i++) {
            sum += graph[iter][i];
        }
        
        return sum;
    }
    
    void insertEdge(int start, int end) {
        graph[start][end] = 1;
        graph[end][start] = 1;
    }
    
    int findBiggestEdgeSum() {
        int bigSum = 0;
        int c_bigSum = 0;
        int manyConnectedVertex = 0;
        
        for(int i=0; i<n; i++) {
            if(visitors[i])
                continue;
            c_bigSum = EdgeSum(i);
            
            if(bigSum < c_bigSum) {
                bigSum = c_bigSum;
                manyConnectedVertex = i;
            }
        }
        
        if(bigSum != 0)
            return manyConnectedVertex;
        
        return -1;
    }
    
};

int main() {
    int T;
    int g, h;
    int s, e;
    int be;
    int noc=0;
    int k;
    
    Graph gr;
    
    std::cin >> T;
    
    while(T > 0) {
        std::cin >> g >> h;
        
        gr.initGraph(g);
        
        for(k=0; k<h; k++) {
            std::cin >> s >> e;
            
            gr.insertEdge(s, e);
        }
        
        // 고립상태 방 조사 및 카메라 추가
        for(k=0; k<g; k++) {
            if(gr.EdgeSum(k) == 0) {
                gr.onVisitors(k);
                noc++;
            }
        }
        
        
        while(gr.visit_yet() == 0) {
            be = gr.findBiggestEdgeSum();
            
            if(be >= 0) {
                noc += gr.BFS(be);
            }
        }
        
        std::cout << noc << "\n";
        noc = 0;
        T--;
    }
    
    return 0;
}

매 케이스마다 방 수를 입력받고 그래프와 방문여부를 조사하는
배열을 초기화합니다.

복도를 입력받는대로 그래프에 추가합니다.

그래프의 한 행의 합이 0인 행 즉 복도가 없는 방을 먼저 조사하여
방문여부배열에 방문을 표시하고 카메라수(noc 변수)를 증가시킵니다.

아직 방문하지 않은 곳이 있을경우 행의 합이 가장 큰 곳을 찾고 거기서 부터 너비 우선 탐색을 진행하며 카메라를 반환합니다.

분명 대부분의 입력에 올바른 답을 반환하는데 문제가 뭔지 감이 안잡힙니다.