It's 2015. Terrorists are still largely on the prowl. Governments however have decided to be
smarter. Now, they monitor each higway, airway and seaway. Across each road, they built
several cameras which can capture images ahead of them.
More specifically, there are N uniformly spaced cameras per kilometer along a highway of
length M kms, making in total M*N cameras (there is no camera at the end of the M kms). The
highway is oneway and goes from North to South. The cameras have a special property:
A camera being destroyed by a terrorist will be caught by cameras to its north. Corrupt
politicians have sold this secret to the terrorists and they know that they can't destroy a camera
unless they are sure that this camera is no longer communicating or being watched by a camera
to its North. There is one further complication: Corrupt technicians have not properly installed
the direct vision equipment. Thus, some of the cameras are substandard and deficient. These
cameras have perfectly good communication with far off cameras (i.e. after the first N cameras),
but cannot see some of the next N cameras. However, the saving grace was that there were no
more than 10 deficient cameras in any 1 km stretch (among any contiguous N cameras).
As Anti Corruption Task force, you, a non corrupt patriot have to submit a security report. For
that, you need to solve the following problem: If exactly two terrorists decide to destroy all the
cameras on the highway without being caught, how long would it take them? Each terrorist can
destroy one camera in one FULL minute. They can work simultaneously. Of course, they cannot
destroy two cameras A and B at the same time if A can watch B or B can watch A.
The cameras are numbered 1 to M*N North to South.
Note that Ci cannot watch or get the video feed of Cj if i > j where Ci is the camera numbered i.
Input will be a sequence of cases. Each case starts with M and N on a single line (1 <= M <= 15
,1 <= N <= 20). M*N - 1 lines follow. The Cth line describes camera number C. It starts with a
number k. If k = -1 camera C is not deficient and there are no more numbers on this line.
Otherwise, k numbers, aj (1<=j<=k) (C+1 <= aj <= C+N and aj <=M*N) follow on the same line
meaning that camera C can watch camera aj. Note that camera C can always watch cameras C +
N + 1 and later using satellite and will not be mentioned here.
The last case will be followed by a line containing two zeroes.
Output one line per case, the minimum number of minutes required by two terrorists working in
tandem to destroy all the cameras without being caught.
Migrated from old NTUJ.
ICPC 2008, Amritapuri
| No. | Testdata Range | Score |
|---|