Connect cities

#![allow(unused)]

use std::{collections::VecDeque, io, mem::take};

struct Node {
    visited: bool,
    neighbors: Vec<usize>,
}

fn take_tuple() -> (usize, usize) {
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    let (a, b) = input.trim().split_once(' ').unwrap();
    (a.parse().unwrap(), b.parse().unwrap())
}

fn create_neighbors(roads: &usize, cities: &usize) -> Vec<Vec<usize>> {
    let mut matrix: Vec<Vec<usize>> = vec![Vec::new(); *cities];

    for _ in 0..*roads {
        let (start, end) = take_tuple();
        matrix[start - 1].push(end - 1);
        matrix[end - 1].push(start - 1);
    }

    matrix
}

fn bfs(
    num_cities: &usize,
    root: usize,
    adjacent: &[Vec<usize>],
    visited: &mut [bool],
) -> usize {
    let mut queue: VecDeque<usize> = VecDeque::with_capacity(*num_cities);
    let mut last: usize = root;

    queue.push_back(root);
    visited[root] = true;

    while !queue.is_empty() {
        let current: usize = queue.pop_front().unwrap();

        for i in adjacent[current].iter() {
            let neighbor = *i;
            if visited[neighbor] {
                continue;
            }
            visited[neighbor] = true;
            queue.push_back(neighbor);
            last = neighbor;
        }
    }

    last
}

fn main() {
    let (num_cities, num_roads) = take_tuple();

    let mut visited: Vec<bool> = vec![false; num_cities];
    let mut adjacent: Vec<Vec<usize>> = create_neighbors(&num_roads, &num_cities);


    // first call
    let mut last = bfs(&num_cities, 0, &adjacent, &mut visited);
    let mut next: usize = 0;
    let mut missing: Vec<(usize, usize)> = Vec::new();

    for i in 0..num_cities {
        if !visited[i] {
            missing.push((last+1, i+1));
            last = bfs(&num_cities, i, &adjacent, &mut visited);
        }
    }
    println!("{}", missing.len());
    for t in missing.iter() {
        println!("{} {}", t.0, t.1);
    }
}

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