TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P4380
  • 题目
  • P4380【wc2016】挑战NPC
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 时限1s 空限256m
    问题描述

    小N最近在研究NP完全问题,小O看小N研究得热火朝天,便给他出了一道这样的题目:

    有n个球,用整数1到n编号。还有m个筐子,用整数1到m编号。

    每个筐子最多能装3个球。

    每个球只能放进特定的筐子中。具体有e个条件,第i个条件用两个整数vi和ui描述,表示编号为vi的球可以放进编号为ui的筐子中。

    每个球都必须放进一个筐子中。如果一个筐子内有不超过1个球,那么我们称这样的筐子为半空的。

    求半空的筐子最多有多少个,以及在最优方案中,每个球分别放在哪个筐子中。

    小N看到题目后瞬间没了思路,站在旁边看热闹的小I嘿嘿一笑:“水题!”

    然后三言两语道出了一个多项式算法。

    小N瞬间就惊呆了,三秒钟后他回过神来一拍桌子:

    “不对!这个问题显然是NP完全问题,你算法肯定有错!”

    小I浅笑:“所以,等我领图灵奖吧!”

    小O只会出题不会做题,所以找到了你——请你对这个问题进行探究,并写一个程序解决此题。

    输入格式

    第一行包含1个正整数T,表示有T组数据。

    对于每组数据,第一行包含3个正整数n,m,e,表示球的个数,筐子的个数和条件的个数。

    接下来e行,每行包含2个整数vi,ui,表示编号为vi的球可以放进编号为ui的筐子。

    输出格式

     对于每组数据,先输出一行,包含一个整数,表示半空的筐子最多有多少个。

    样例输入

    1
    4 3 6
    1 1
    2 1
    2 2
    3 2
    3 3
    4 3

    样例输出

    2

    提示

    对于所有数据,T≤5,1≤n≤3m。保证 1≤vi≤n,1≤ui≤m,且不会出现重复的条件。

    保证至少有一种合法方案,使得每个球都放进了筐子,且每个筐子内球的个数不超过 3。

    M<=100