TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • 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