Connect cities

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

int checkVisited(const vector<bool>& visited){
    for(unsigned int i=0; i< visited.size(); i++){
        if(visited[i]==false) return i;
    }
    return -1;
}

vector<pair<int,int>> BFS(vector<bool>& visited, vector<vector<int>>& roads, const int& init){
    vector<pair<int,int>> addedRoads;

    stack<int> q;
    q.push(init);

    while(not q.empty())
    {
        int x = q.top();
        q.pop();
        for(unsigned int i=0; i<roads[x].size(); i++){
            if(visited[roads[x][i]] == false) q.push(roads[x][i]);
        }
        visited[x] = true;

        if(q.empty()){
            int ll = checkVisited(visited);
            if(ll == -1) return addedRoads;

            roads[ll].push_back(x);
            roads[x].push_back(ll);

            q.push(ll);

            addedRoads.push_back(make_pair(x,ll));
        }
    }

    return addedRoads;
}

int main(){
    unsigned int n,m;
    cin >> n >> m;

    vector<bool> visited(n, false);
    vector<vector<int>> roads(n);

    for(unsigned int i=0; i<m; i++){
        int a,b;
        cin >> a >> b;
        roads[a-1].push_back(b-1);
        roads[b-1].push_back(a-1);
    }

    
    vector<pair<int,int>> res = BFS(visited, roads, 0);

    cout << res.size() << endl;

    for(unsigned int i=0; i<res.size(); i++){ 
        cout << res[i].first +1 <<" "<< res[i].second+1;
        cout << endl;
    }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: TIME LIMIT EXCEEDED

Test 12

Verdict: ACCEPTED