控制 - 代码源竞赛平台

题目描述

实验室有 $n$ 台控制器和 $m$ 台设备。控制器编号为 $1$ 至 $n$，设备编号为 $1$ 至 $m$，两类编号分别使用。

每台设备关联着若干台控制器。工作人员准备选出两台不同的控制器进行联调：如果一台设备关联的所有控制器都被选中，这台设备就能完成检查。没有关联任何控制器的设备也视为能够完成检查。

怎样选择这两台控制器，才能让完成检查的设备数量最多？输出这个最大数量。

输入格式

第一行包含两个正整数 $n,m$ 和一个非负整数 $e$，分别为控制器数量、设备数量和关联记录的数量。

接下来 $e$ 行，每行包含两个正整数 $u,v$，表示控制器 $u$ 与设备 $v$ 关联。同一台控制器与同一台设备之间至多有一条关联记录。

输出格式

输出一个非负整数，表示选出两台不同的控制器后，最多能够完成检查的设备数量。

样例

3 8 12
1 2
1 3
2 4
2 5
3 5
2 6
3 6
2 7
3 7
1 8
2 8
3 8

5

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

4

样例解释

样例 1：选择控制器 $2,3$，设备 $1,4,5,6,7$ 能够完成检查。其中设备 $1$ 没有关联任何控制器。

样例 2：选择控制器 $1,2$，设备 $1,2,3,4$ 能够完成检查。

数据规模

本题各子任务单独计分。须通过某子任务包含的所有测试点，方可获得该子任务的分数。

子任务编号	分数	$n\le$	特殊性质
$1$	$30$	$60$	A
$2$	$20$	$2\times 10^5$	B
$3$	$50$		无

特殊性质 A：$m\le 60$。

特殊性质 B：每台设备至多关联一台控制器。

对于 $100\%$ 的数据，$2\le n\le 2\times 10^5$，$1\le m\le 2\times 10^5$，$0\le e\le 2\times 10^5$，$1\le u\le n$，$1\le v\le m$，且同一台控制器与同一台设备之间至多有一条关联记录。