ALL  All Discs Considered
Operating systems are large software artefacts composed of many packages, usually distributed on several media, e.g., discs. You probably remember the time when your favourite operating system was delivered on 21 floppy discs, or, a few years later, on 6 CDs. Nowadays, it will be shipped on several DVDs, each containing tens of thousands of packages.
The installation of certain packages may require that other packages have been installed previously. Therefore, if the packages are distributed on the media in an unsuitable way, the installation of the complete system requires you to perform many media changes, provided that there is only one reading device available, e.g., one DVDROM drive. Since you have to start the installation somehow, there will of course be one or more packages that can be installed independently of all other packages.
Given a distribution of packages on media and a list of dependences between packages, you have to calculate the minimal number of media changes required to install all packages. For your convenience, you may assume that the operating system comes on exactly 2 DVDs.
Input
The input contains several test cases.
Every test case starts with three integers N_{1}, N_{2}, D
.
You may assume that 1<=N_{1},N_{2}<=50000
and 0<=D<=100000
.
The first DVD contains N_{1}
packages, identified by the numbers 1, 2, ..., N_{1}
.
The second DVD contains N_{2}
packages, identified by the numbers N_{1}+1, N_{1}+2, ..., N_{1}+N_{2}
.
Then follow D
dependence specifications, each consisting of two integers x_{i}, y_{i}
.
You may assume that 1<=x_{i},y_{i}<=N_{1}+N_{2}
for 1<=i<=D
.
The dependence specification means that the installation of package x_{i}
requires the previous installation of package y_{i}
.
You may assume that there are no circular dependences.
The last test case is followed by three zeros.
Output
For each test case output on a line the minimal number of DVD changes required to install all packages.
By convention, the DVD drive is empty before the 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 DVD drive empty after the installation.
Example
Input: 3 2 1 1 2 2 2 2 1 3 4 2 2 1 1 1 3 0 0 0 Output: 3 4 3
hide comments
nadstratosfer:
20190424 22:40:41
Great problem. Had a hard time trying to crack it using BFS only until I remembered another code dealing with multiple dependencies I had written a year ago. PyPy passes the TL but like Simes said, avoid linebased reading. 

Simes:
20171117 20:11:57
I think some of the input data is malformed. I found the original test data, and that has test cases formatted like:


mastik5h_1998:
20170705 03:37:28
can anyone explain test case


vikas:
20150620 13:27:36
many to one dependency can be there 

hatim ali:
20150205 17:36:47
what's this


Mr Tambourine Man:
20140515 00:04:10
can someone provide more test cases? my code seems to be working on all the cases I tried. Getting WA :( 

RAHUL RANJAN:
20131204 14:57:49
easy one Last edit: 20131204 16:18:58 

henry homers:
20130608 21:28:56
good one..... but disappointed at my poor code... 

Alex Anderson:
20130116 21:48:29
Needs good Java I/O to solve. 

Termvader:
20120425 20:19:45
Can a package have more than one dependency?

Added by:  Wanderley GuimarÄƒes 
Date:  20070914 
Time limit:  0.343s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO 
Resource:  University of Ulm Local Contest 2004 