Building Teams

#![allow(unused)]

use std::{collections::VecDeque, io, process::exit};

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_nodes: &usize, root: usize, adjacent: &[Vec<usize>], visited: &mut [bool], colors: &mut [usize]) -> usize {
    let mut queue: VecDeque<usize> = VecDeque::with_capacity(*num_nodes);
    let mut last: usize = root;

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

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

        for i in adjacent[current].iter() {
            let neighbor = *i;
            if visited[neighbor] {
                if current_color == colors[neighbor] {
                    println!("IMPOSSIBLE");
                    exit(0);
                }
                continue;
            }
            visited[neighbor] = true;


            queue.push_back(neighbor);
            last = neighbor;

            if current_color == 1 {
                colors[neighbor] = 2;
            } else {
                colors[neighbor] = 1;
            }
        }
    }

    last
}


fn take_tuple() -> (usize, usize) {
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    let mut it = input.trim().split_whitespace().map(|x| x.parse::<usize>().unwrap());
    (it.next().unwrap(), it.next().unwrap())
}

fn main() {
    let (num_nodes, num_edges) = take_tuple();

    let mut visited: Vec<bool> = vec![false; num_nodes];
    let mut colors: Vec<usize> = vec![0; num_nodes];
    let mut adjacent: Vec<Vec<usize>> = create_neighbors(&num_edges, &num_nodes);


    // first call
    colors[0] = 1;
    let mut last = bfs(&num_nodes, 0, &adjacent, &mut visited, &mut colors);

    let mut next: usize = 0;
    let mut missing: Vec<(usize, usize)> = Vec::new();

    for i in 0..num_nodes {
        if !visited[i] {
            colors[i] = 1;
            missing.push((last+1, i+1));
            last = bfs(&num_nodes, i, &adjacent, &mut visited, &mut colors);
        }
    }
    for color in colors.iter() {
        print!("{} ", color);
    }
}

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