All Discs Considered

An operating system is a large piece of software made up of many packages, which are usually shipped across several media — for example, discs. Long ago your favorite operating system might have arrived on 21 floppy disks, and a few years later on 6 CDs; today it ships on several DVDs, each holding tens of thousands of packages.

Installing some packages requires that other packages already be installed. If the packages are laid out across the media poorly, installing the whole system forces many media changes, because only one reading device is available — a single DVD-ROM drive. Since the installation has to start somewhere, there is always at least one package that can be installed without any other package being present first.

Given how the packages are distributed across the media and the list of dependencies between them, compute the minimum number of media changes needed to install every package. For simplicity, assume the operating system ships on exactly $2$ DVDs.

The input contains several test cases. Each test case begins with three integers $N_1$, $N_2$, $D$, where $1 \le N_1, N_2 \le 50000$ and $0 \le D \le 100000$. The first DVD holds $N_1$ packages numbered $1, 2, \ldots, N_1$. The second DVD holds $N_2$ packages numbered $N_1+1, N_1+2, \ldots, N_1+N_2$.

Then follow $D$ dependency specifications, each consisting of two integers $x_i$, $y_i$ with $1 \le x_i, y_i \le N_1+N_2$. Such a specification means that installing package $x_i$ requires package $y_i$ to be installed first. You may assume there are no circular dependencies.

The last test case is followed by a line containing three zeros, which must not be processed.

For each test case, print on its own line the minimum number of DVD changes required to install all packages.

By convention the drive is empty before installation, and the initial insertion of a disc counts as one change; likewise the final removal of a disc counts as one change, leaving the drive empty afterward.