题目描述

操作系统是由许多软件包组成的大型软件产品，通常分布在多个介质（如磁盘）上。你可能还记得，过去你喜欢的操作系统需要用21张软盘安装，或者几年后用6张CD安装。如今，它可能通过几张DVD发行，每张DVD包含数以万计的软件包。

安装某些软件包可能需要先安装其他软件包。因此，如果软件包在介质上的分布方式不合适，在只有一个读取设备（如一个DVD-ROM驱动器）的情况下，安装整个系统需要频繁更换介质。当然，安装过程必须从某些可以独立安装（不依赖其他软件包）的软件包开始。

给定软件包在两张DVD上的分布情况和依赖关系列表，你需要计算安装所有软件包所需的最小介质更换次数。为了简化问题，假设操作系统恰好通过两张DVD发行。

输入格式

输入包含多个测试用例。每个测试用例以三个整数$N_1$、$N_2$、$D$开始。其中，$1 \leq N_1, N_2 \leq 50000$，$0 \leq D \leq 100000$。第一张DVD包含$N_1$个软件包，编号为$1, 2, \ldots, N_1$；第二张DVD包含$N_2$个软件包，编号为$N_1+1, N_1+2, \ldots, N_1+N_2$。接下来是$D$条依赖关系，每条关系由两个整数$x_i$、$y_i$表示，表示安装软件包$x_i$前必须先安装软件包$y_i$。保证不存在循环依赖。最后一个测试用例后接三个0。

输出格式

对每个测试用例，输出一行表示安装所有软件包所需的最小DVD更换次数。约定：安装前驱动器为空，初始插入光盘算作一次更换；安装结束后取出光盘也算作一次更换，最终驱动器为空。

输入示例1

3 2 1  
1 2  
2 2 2  
1 3  
4 2  
2 1 1  
1 3  
0 0 0  

输出示例1

3  
4  
3  

来源

Ulm Local 2004