AtCoder Beginner Contest 435 D

https://atcoder.jp/contests/abc435/tasks/abc435_d

黒いノードをいちいち探していたら、そのたびにO(N)かかるので、間に合いません。
そうでなくて、黒くするたびに逆に辿っておけば、合計でO(N)しかかかりません。

// Reachability Query 2
#![allow(non_snake_case)]


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}

fn YesNo(b: bool) -> String {
    return if b { "Yes" } else { "No" }.to_string()
}


//////////////////// Graph ////////////////////

type Node = usize;
type Edge = (Node, Node);

fn read_edge() -> Edge {
    let v: Vec<usize> = read_vec();
    (v[0]-1, v[1]-1)
}

struct Graph {
    g: Vec<Vec<Node>>,
}

impl Graph {
    fn neighbors(&self, v: Node) -> &Vec<Node> {
        &self.g[v]
    }
    
    fn inverse(&self) -> Graph {
        let N = self.g.len();
        let mut g: Vec<Vec<Node>> = vec![vec![]; N];
        for u in 0..N {
            for &v in self.g[u].iter() {
                g[v].push(u)
            }
        }
        Graph { g }
    }
    
    fn create(N: usize, edges: Vec<Edge>) -> Graph {
        let mut g: Vec<Vec<Node>> = vec![vec![]; N];
        for (X, Y) in edges {
            g[X].push(Y);
        }
        Graph { g }
    }
}


//////////////////// BWGraph ////////////////////

struct BWGraph {
    inv_graph: Graph,
    blacks: Vec<bool>,
}

impl BWGraph {
    fn change(&mut self, v: Node) {
        self.walk_black(v)
    }
    
    fn print(&self, v: Node) {
        println!("{}", YesNo(self.blacks[v]))
    }
    
    fn walk_black(&mut self, v0: Node) {
        let mut stack: Vec<Node> = vec![v0];
        while let Some(v) = stack.pop() {
            if self.blacks[v] {
                continue
            }
            self.blacks[v] = true;
            for &v1 in self.inv_graph.neighbors(v).iter() {
                if !self.blacks[v1] {
                    stack.push(v1)
                }
            }
        }
    }
    
    fn create(N: usize, edges: Vec<Edge>) -> BWGraph {
        let graph = Graph::create(N, edges);
        let inv_graph = graph.inverse();
        let blacks: Vec<bool> = vec![false; N];
        BWGraph { inv_graph, blacks }
    }
}


//////////////////// Query ////////////////////

enum Query {
    Change(usize),
    Print(usize)
}

impl Query {
    fn read() -> Query {
        let v: Vec<usize> = read_vec();
        if v[0] == 1 {
            Query::Change(v[1]-1)
        }
        else {
            Query::Print(v[1]-1)
        }
    }
}


//////////////////// process ////////////////////

fn read_input() -> (usize, Vec<Edge>, usize) {
    let v: Vec<usize> = read_vec();
    let (N, M) = (v[0], v[1]);
    let edges: Vec<Edge> = (0..M).map(|_| read_edge()).collect();
    let Q: usize = read();
    (N, edges, Q)
}

fn F(N: usize, edges: Vec<Edge>, Q: usize) {
    let mut graph = BWGraph::create(N, edges);
    for _ in 0..Q {
        match Query::read() {
            Query::Change(v) => graph.change(v),
            Query::Print(v)  => graph.print(v)
        }
    }
}

fn main() {
    let (N, edges, Q) = read_input();
    F(N, edges, Q)
}