Connect cities

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

int main() {
    int n, m;
    std::cin >> n >> m;

    std::vector<std::pair<int, int>> roads(m);
    for (int i = 0; i < m; ++i) {
        int a, b;
        std::cin >> a >> b;
        roads[i] = std::make_pair(a-1, b-1);
    }
    //std::sort(roads.begin(), roads.end());

    int num_components = 1;
    std::vector<int> component(n, 0);
    std::vector<int> component_heads;
    component[0] = 1;
    component_heads.push_back(0);
    
    std::queue<int> search_queue;
    search_queue.push(0);
    int traversed = 0;
    while (traversed != n) {
        if (search_queue.empty()) {
            for (int i = 0; i < n; ++i) {
                if (component[i] == 0) {
                    search_queue.push(i);
                    num_components++;
                    component[i] = num_components;
                    component_heads.push_back(i);
                    break;
                }
            }
        }

        int city = search_queue.front();
        search_queue.pop();
        for (int i = 0; i < m; ++i) {
            if (roads[i].first == city) {
                int new_city = roads[i].second;
                if (component[new_city] != 0) continue;
                search_queue.push(new_city);
                component[new_city] = num_components;
            }
        }
        traversed++;
    }

    std::cout << num_components-1 << std::endl;
    for (int i = 0; i < num_components-1; ++i) {
        std::cout << component_heads[i]+1 << " " << component_heads[i+1]+1 << std::endl;
    }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: WRONG ANSWER

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: TIME LIMIT EXCEEDED

Test 10

Verdict: TIME LIMIT EXCEEDED

Test 11

Verdict: TIME LIMIT EXCEEDED

Test 12

Verdict: ACCEPTED