問題一覧 > 通常問題

No.1703 Much Matching

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 95
作問者 : harurunharurun / テスター : saksak
1 ProblemId : 6929 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-09-14 13:08:10

問題文

harurun 王国には $1\sim N$ の番号が付いた $N$ 人の男性と $1\sim M$ の番号が付いた $M$ 人の女性がいます。

国王のharurun君は 男女のペアをできるだけ多く作ろうとしています。

以下の条件を全て満たすようにペアを作ったとき、最大で何ペアできますか?

条件

  • 複数のペアに同じ人が属することはできない。

  • $Q$ 個の要素の配列 $a,b$ が与えられる。男性 $a_i$ と女性 $b_j$ がペアを作れるのは、$i=j$ のときに限る。

  • 作った $i$ 番目のペアを $C_i=(x_i,y_i)$ としたとき、$i<j$ ならば $x_i<x_j$ かつ $y_i<y_j$ でなければならない。

    ( $x_i$ は男性を、 $y_i$ は女性を表す)

入力

$N\ M\ Q$
$a_1\ b_1$
$\vdots$
$a_Q\ b_Q$
  • $1$ 行目は $N$,$M$,$Q$ が空白区切りで与えられる

  • $2\sim Q+1$ 行目は $a_i$,$b_i$ が空白区切りで与えられる

制約

  • $1≤N,M≤10^3$

  • $1≤Q≤N\times M$

  • $1≤a_i≤N$

  • $1≤b_i≤M$

  • $i\neq j$ のとき $(a_i,b_i)\neq(a_j,b_j)$

  • 入力は全て整数

出力

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

サンプル

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

1人ずつしかいないです。この王国は大丈夫でしょうか。

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

$C=((1,2),(2,3))$ です。

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

$C=((1,2),(2,3))$ です。

3つ目の条件より $C=((1,2),(2,3),(3,1))$ にできないことに注意してください。

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