#P17702. [2026年江苏省队集训]众

[2026年江苏省队集训]众

题面描述

给定一张由 nn 个左部点和 mm 个右部点组成的,包含 kk 条边的简单二分图。

定义一组匹配为点对 (l1,l2,r)(l_1,l_2,r) 满足 l1l_1 和 l2l_2 是左部点,rr 是右部点,且 l1l_1 和 l2l_2 均与 rr 有边相连。

求图的最大匹配大小。换句话说,找到尽量多组匹配,满足任意两组匹配不共用顶点。无需输出方案。

输入格式

输入的第一行包含一个正整数 tt,表示测试数据组数。

每组测试数据的第一行包含三个非负整数 n,m,kn,m,k。

接下来 kk 行每行包含两个整数 l,rl,r,表示一条连接第 ll 个左部点和第 rr 个右部点的边。

输出格式

输出 tt 行每行一个整数,表示最大匹配的大小。

样例输入与输出

1
6 3 10
3 1
4 1
1 2
2 2
3 2
4 2
5 2
6 2
3 3
4 3
2

样例解释

一种方案是选择 (3,4,1)(3,4,1) 和 (1,2,2)(1,2,2) 两组匹配。

数据范围与子任务

对于所有数据,满足 1≤t≤201\leq t\leq 20,1≤n,∑n≤5001\leq n,\sum n\leq 500,1≤m,∑m≤1051\leq m,\sum m\leq 10^5,0≤k,∑k≤1050\leq k,\sum k\leq 10^5。

子任务编号 子任务分值 特殊性质
11 1010 n≤8n\leq 8
22 1515 所有右部点的度数均为 22
33 3030 ∑n+∑m≤150\sum n+\sum m\leq 150
44 1515 每条边的端点在所有点中均匀随机
55 3030 无特殊限制

其中子任务 44 的随机方式为:每条边不断均匀随机端点编号直到该边没有出现过。