問題一覧 > 通常問題

No.1669 パズル作成

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 16
作問者 : 沙耶花沙耶花 / テスター : penguinmanpenguinman
10 ProblemId : 5998 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-05-02 15:30:39

問題文

$N \times N$ のマス目があります.
はじめ, $i=1,2,...,M$ に対し $r_i$ 行 $c_i$ 列目のマスは黒く, 残る $N^2 - M$ 個のマスは白いです.

まず, あなたは次の操作を好きな回数($0$ 回でもよい)行えます.

  • 操作$X$: 白いマスを $1$ つ選び, 黒くする

    • その後, あなたは次の $2$ 種類の操作を好きな順番で好きな回数(やはり $0$ 回でもよい)行えます.
  • 操作$Y$: 好きな行を $1$ つ選び, そこに属するマスの色を反転(白なら黒に, 黒なら白に変更)する
  • 操作$Z$: 好きな列を $1$ つ選び, そこに属するマスの色を反転する

    • すべてのマスを黒くするために, 操作$X$は最小で何回必要ですか？

    入力

    $N\ M$
$r_1\ c_1$
$\vdots$
$r_M\ c_M$

  • $1 \le N \le 5000$
  • $0 \le M \le \min (10^5, N^2)$
  • $1 \le r_i,c_i \le N$
  • $i \ne j$ ならば $(r_i,c_i) \ne (r_j,c_j)$
  • 入力はすべて整数

    • 出力

    答えを出力してください.
    最後に改行してください.

    サンプル

    サンプル1
    入力
    2 1
1 2
    出力
    1

    $1$ 行 $1$ 列目に操作 $X$ を行い, $2$ 行目に操作 $Y$ を行うことですべてのマスを黒くできます.

    サンプル2
    入力
    2 0
    出力
    0

    サンプル3
    入力
    4 5
1 1
2 2
3 2
4 1
1 2
    出力
    3

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。