N行N列の盤面が与えられる。盤面の左からx番目、盤面の上からy番目のマスを(x,y)と表す。この盤面にはコマを置けるマスの候補(a_i,b_i)がM個存在する。
Q個のクエリが与えられる。クエリではマス(x_i,y_i)が与えられ、コマを置けるマスならばコマを置けないマスに変化し、コマを置けないマスならばコマを置けるマスへ変化する。この変化した後の盤面において、コマをN個置くことで、どの行・列についてもコマがちょうど1個存在するようにできるのであればYes
、置けないのであればNo
を出力しろ。
N M a_1 b_1 a_2 b_2 ... a_M b_M Q x_1 y_1 x_2 y_2 ... x_M y_M
各クエリについてYes
かNo
を出力しろ。
5 4 4 1 1 2 2 3 5 4 1 3 5
Yes
コマを置けるマスをo、置けないマスをxとしたときの盤面を以下に示す。oのマスにコマを1つずつ置けば条件を満たす。
xxxox oxxxx xoxxx xxxxo xxoxx