Connect cities

#include<iostream>
#include<queue>
#include <unordered_map>
#include <set>
#include <utility>

typedef long long ll;
using namespace std;


int main()
{   
    ll cities, roads;

    cin >> cities >> roads;

    vector<ll> adj[cities + 1];

    ll a, b;

    while (cin >> a >> b)
    {
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    vector<bool> visited(cities + 1, false);
    vector<vector<ll>> clusters;

    for (int c = 1; c <= cities; ++c)
    {
        if (visited[c])
        {
            continue;
        }
        else
        {   
            queue<ll> q;
            q.push(c);
            vector<ll> cluster;
            
            while (!q.empty())
            {
                ll node = q.front();
                q.pop();
                visited[node] = true;
                cluster.push_back(node);

                for (const auto b : adj[node])
                {
                    if (!visited[b])
                    {
                        q.push(b);
                    }
                }
            }

            clusters.push_back(cluster);
        }
    }

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


    return 0;
}

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: ACCEPTED

Test 12

Verdict: ACCEPTED