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*2);
    for (int i = 0; i < m; ++i) {
        int a, b;
        std::cin >> a >> b;
        //if (a > b) std::swap(a, b);
        roads[i*2] = std::make_pair(a-1, b-1);
        roads[i*2+1] = std::make_pair(b-1, a-1);
    }
    //std::sort(roads.begin(), roads.end());

    std::vector<bool> visited(n, false);
    std::vector<int> component_heads;
    std::queue<int> search_queue;
    
    for (int i = 0; i < n; ++i) {
        if (search_queue.empty()) {
            for (int j = 0; j < n; ++j) {
                if (visited[j]) continue; 
                search_queue.push(j);
                visited[j] = true;
                component_heads.push_back(j);
                break;
            }
        }

        int city = search_queue.front();
        search_queue.pop();
        for (int j = 0; j < m*2; ++j) {
            if (roads[j].first == city) {
                int new_city = roads[j].second;
                if (visited[new_city]) continue;
                search_queue.push(new_city);
                visited[new_city] = true;
            }
        }
    }

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

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

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