SPOJ.com - Problem ALL

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 DVD-ROM 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₁, N₂, D. You may assume that 1<=N₁,N₂<=50000 and 0<=D<=100000. The first DVD contains N₁ packages, identified by the numbers 1, 2, ..., N₁. The second DVD contains N₂ packages, identified by the numbers N₁+1, N₁+2, ..., N₁+N₂. Then follow D dependence specifications, each consisting of two integers x_i, y_i. You may assume that 1<=x_i,y_i<=N₁+N₂ 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

Submit solution!

Added by:	Wanderley Guimarăes
Date:	2007-09-14
Time limit:	1s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ERL JS-RHINO
Resource:	University of Ulm Local Contest 2004

hide comments

2019-04-24 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 line-based reading.

2017-11-17 20:11:57 Simes
I think some of the input data is malformed. I found the original test data, and that has test cases formatted like:
2 1 2 1 2 1 3
instead of
2 1 2
1 2
1 3
as shown in the examples here. I got wrong answer when I used Pascal "readln" and accepted when I used "read".

Last edit: 2017-11-17 20:55:24

2017-07-05 03:37:28
can anyone explain test case
3 2 1
1 2

how come the ans is 3

2015-06-20 13:27:36 vikas
many to one dependency can be there

2015-02-05 17:36:47 hatim ali
what's this

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

2013-12-04 14:57:49 RAHUL RANJAN
easy one

Last edit: 2013-12-04 16:18:58

2013-06-08 21:28:56 henry homers
good one..... but disappointed at my poor code...

2013-01-16 21:48:29 Alex Anderson
Needs good Java I/O to solve.

2012-04-25 20:19:45 Termvader
Can a package have more than one dependency?
like
2 2 2
1 3
1 4

EDIT: Yes it does

Last edit: 2012-04-25 22:39:59