普通に幅優先探索で塗る.

ただし, クエリの数が多いので, 途中で全マスが同じ色になることがあり, その場合は以降は全部塗るのを繰り返すのでいちいち計算しないようにする.