Connect cities

#include "iostream"
#include "vector"


int main() {
    int n, m;
    std::cin >> n >> m;
    if (1 > n || n > 100000 || 1 > m || m > 200000) return EXIT_FAILURE;
    std::vector<std::vector <int>> roads = {};
    int a, b;
    for (int i = 1; i <= m; i++) {
        std::cin >> a >> b;
        if ((1 <= a) && (a <= n) && (1 <= b) && (b <= n)) {
            roads.push_back(std::vector<int>{a, b});
        }
    }
    std::vector<int> neighbors = {1};
    int k = 0;
    std::vector<std::vector<int>> newRoads;
    std::vector<int> visited;
    for (int i = 1; i <= n; i++) {
        visited.push_back(i);
    }
    bool allVisited = false;
    while (!neighbors.empty() && !allVisited) {
        int curr = neighbors.back();
        neighbors.pop_back();
        visited[curr - 1] = -1;
        for (int i = 0; i < m; i++) {
            if (roads[i].front() == curr && visited[roads[i].front()] != -1) neighbors.push_back(roads[i].back());
            else if (roads[i].back() == curr && visited[roads[i].back()] != -1) neighbors.push_back(roads[i].front());
        }
        if (neighbors.empty()) {
            int i = 1;
            while (i <= n) {
                if (visited.at(i-1) != -1) {
                    neighbors.push_back(i);
                    k++;
                    newRoads.push_back(std::vector<int>{curr, i});
                    break;
                }
                i++;
            }
            if (i == n && neighbors.empty()) allVisited = true; 
        }
    }

    std::cout << k << std::endl;
    for (int i = 0; i < k; i++) {
        std::cout << newRoads[i].front() << " " << newRoads[i].back() << std::endl;
    }
}

Test 1

Verdict: TIME LIMIT EXCEEDED

Test 2

Verdict: TIME LIMIT EXCEEDED

Test 3

Verdict: TIME LIMIT EXCEEDED

Test 4

Verdict: TIME LIMIT EXCEEDED

Test 5

Verdict: TIME LIMIT EXCEEDED

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: TIME LIMIT EXCEEDED