差が \(d=2\) である2マスに書き込まれる整数の偶奇は一致する必要があり，差が \(d=1\) である2マスに書き込まれる整数の偶奇は異なる必要があります．この時点で矛盾が存在すれば，答えは No です．この判定は，二部グラフ判定の要領で \(O(N^2)\) 時間で行えます．

矛盾がないとき，答えは必ず Yes です．以下のようにして，\(0\) 以上 \(3\) 以下の整数のみを書き込んで条件を満たすことができます．

1. 各マスに書き込む整数の偶奇を矛盾がないように決める
2. 各マス \((i,j)\) について，以下のルールに従って整数を書き込む
   • 偶数を書き込む場合
     • \(i+j\) が偶数なら， \(0\) を書き込む
     • \(i+j\) が奇数なら， \(2\) を書き込む
   • 奇数を書き込む場合
     • \(i+j\) が偶数なら， \(3\) を書き込む
     • \(i+j\) が奇数なら， \(1\) を書き込む

この書き込み方が条件を満たすことを確かめます．隣接するマスの \(i+j\) の偶奇は異なるため，同じ数字が隣接することや，\(0\) と \(3\) が隣接することはありません．よって，隣接するマスに書き込まれる整数の差は \(1\) か \(2\) です．また，偶奇に矛盾はないため，与えられた \(M\) 個の条件もすべて満たします．