TouchStone
  Please Login
ログイン 登録
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P1606
  • 問題
  • P1606排雷
    制限 : 時間制限 : 10000 MS   メモリ制限 : 65536 KB
    問題説明

    一队士兵在巡逻时发现在他们的一条必经之路上被埋上了地雷。工兵发现,地雷埋在公路的左右两侧,而且公路两侧的一些地雷有细线相连,只要拆除一颗地雷,公路另一边跟它通过细线相连的所有地雷就会爆炸。
       工兵还发现地雷具有这些特点:一个地雷爆炸不会影响跟它相连的地雷。两个雷之间可能有多条细线相连。细线只连接位于公路两侧的地雷,同一侧的地雷没有细线相连。
       为了避免公路被炸毁,工兵想拆掉尽可能多的地雷,问:工兵最多可拆掉多少地雷?

    入力形式

    第一行包括三个整数N1,N2和M,分别表示左侧地雷数,右侧地雷数和细线总数。(左右两边的地雷分别按1..N1和1..N2标号)
    接下来有M行,每行有两个整数A,B(1<=A<=N1,1<=B<=N2),表示左边的地雷A和右边的地雷B有一条细线相连。

    出力形式

    一整数表示能拆掉的最大地雷数

    サンプル入力

    3 3 5
    1 2
    2 1
    2 2
    2 3
    3 2

    サンプル出力

    4

    ヒント

    工军拆掉了左侧的1、3和右侧的1、3号地雷。

    100%的数据 V<=1000 0<=N1,N2<=500 M<=250,000