083 - Colorful Graph（★6）
次数の小さい頂点については愚直に処理できるが、次数のデカい頂点について何度も聞かれるとヤバい
平方分割を考え、次数が$ B=\sqrt N 以下と超過で場合分けする
次数が$ B以下ならそのまま処理すればよい
$ Bより多いなら、その頂点に「何番目のクエリでどの色に更新したか」という旗を立てておく
各クエリで頂点の色を答える場合、自分と隣接している頂点について旗が建てられているか見に行く必要があるが、旗が建てられうる頂点は限られているのであらかじめ候補を計算しておくことができる
これがまんま類題