Connect cities

warning: unused import: `std::cmp::min`
 --> input/code.rs:1:5
  |
1 | use std::cmp::min;
  |     ^^^^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: unused import: `std::collections::VecDeque`
 --> input/code.rs:2:5
  |
2 | use std::collections::VecDeque;
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^^

warning: 2 warnings emitted

use std::cmp::min;
use std::collections::VecDeque;
use std::io::{self, Read};

macro_rules! input {
    ($it: expr) => {
        $it.next().unwrap().parse().unwrap()
    };
    ($it: expr, $T: ty) => {
        $it.next().unwrap().parse::<$T>().unwrap()
    };
}
/*
mod classes;
mod homework;

fn main() {
    // println!("{}", "-".repeat(20));
    // classes::c03::task1();
    homework::hw1::task1();
    // println!("{}", "-".repeat(20));
}
// */

fn main() {
    task();
}

#[allow(dead_code)]
fn task() {
    let mut buf = String::new();
    io::stdin().read_to_string(&mut buf).unwrap();

    let mut it = buf.split_whitespace();

    let (n, m): (usize, usize) = (input!(it), input!(it));

    let mut g:Vec<Vec<usize>> = vec![vec![]; n+1];

    for _ in 1..m+1 {
        let (v, u): (usize, usize) = (input!(it), input!(it));
        g[v].push(u);
        g[u].push(v);
    }

    let mut visited = vec![false; n+1];
    let mut components = vec![];

    for i in 1..=n {
        if !visited[i] {
            let mut component = Vec::new();
            dfs(i, &mut visited, &g, &mut component);
            if !component.is_empty() {
                components.push(component);
            }
        }
    }


    println!("{}", components.len()-1); // missing edges

    if components.len() > 1 {
        for i in 0..components.len()-1 {
            let u = components[i][components[i].len()-1]; // Last node from current component
            let v = components[i+1][0]; // First node from next component
            println!("{} {}", u, v);
        }
    }
}

fn dfs(v: usize, visited: &mut Vec<bool>, g: &Vec<Vec<usize>>, component: &mut Vec<usize>) {
    visited[v] = true;
    component.push(v);

    for &u in &g[v] {
        if !visited[u] {
            dfs(u, visited, g, component);
        }
    }
}

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