のマス目がある。上から 行目、左から 列目のマスを とする。
2つのマスが1辺を共有するとき、それらは 隣接しているという。すなわち、 と が隣接するための必要十分条件は である。
すべてのマスを のいずれかの色で塗る。塗り分けは次の条件をすべて満たさなければならない。
制約を満たすすべての入力について、この条件を満たす塗り分けが少なくとも1つ存在することを証明できる。条件を満たす塗り分けを1つ求めよ。
入力は標準入力から次の形式で与えられる。
行にわたって塗り分けを出力せよ。 行目には 個の整数 を空白区切りで出力する。 はマス の色を表す。
出力した塗り分けは問題文のすべての条件を満たさなければならない。条件を満たす出力が複数存在する場合、そのうちどれを出力してもよい。