**********************************************************************
                           SILVER PROBLEMS
**********************************************************************
                  Three problems numbered 6 through 8
**********************************************************************

Problem 6: Part Acquisition [Coaches, 2004]

The cows have been sent on a mission through space to acquire a new
milking machine for their barn.  They are flying through a cluster
of stars containing N (1 <= N <= 50,000) planets, each with a trading
post.

The cows have determined which of K (1 <= K <= 1,000) types of
objects (numbered 1..K) each planet in the cluster desires, and
which products they have to trade. No planet has developed currency,
so they work under the barter system: all trades consist of each
party trading exactly one object (presumably of different types).

The cows start from Earth with a canister of high quality hay (item
1), and they desire a new milking machine (item K). Help them find
the best way to make a series of trades at the planets in the cluster
to get item K.  If this task is impossible, output -1.

PROBLEM NAME: acquire

INPUT FORMAT:

* Line 1: Two space-separated integers, N and K.

* Lines 2..N+1: Line i+1 contains two space-separated integers, a_i
        and b_i respectively, that are planet i's trading trading
        products. The planet will give item b_i in order to receive
        item a_i.

SAMPLE INPUT (file acquire.in):

6 5
1 3
3 2
2 3
3 1
2 5
5 4

OUTPUT FORMAT:

* Line 1: One more than the minimum number of trades to get the
        milking machine which is item K (or -1 if the cows cannot
        obtain item K).

* Lines 2..T+1: The ordered list of the objects that the cows possess
        in the sequence of trades.

SAMPLE OUTPUT (file acquire.out):

4
1
3
2
5

OUTPUT DETAILS:

The cows possess 4 objects in total: first they trade object 1 for
object 3, then object 3 for object 2, then object 2 for object 5.

**********************************************************************

Problem 7: Rigging the Bovine Election [Coaches, 2004]

It's election time. The farm is partitioned into a 5x5 grid of cow
locations, each of which holds either a Holstein ('H') or Jersey
('J') cow.  The Jerseys want to create a voting district of 7 contiguous
(vertically or horizontally) cow locations such that the Jerseys outnumber
the Holsteins. How many ways can this be done for the supplied grid?

PROBLEM NAME: cowrig

INPUT FORMAT:

* Lines 1..5: Each of the five lines contains five characters per
        line, each 'H' or 'J'.  No spaces are present.

SAMPLE INPUT (file cowrig.in):

HHHHH
JHJHJ
HHHHH
HJHHJ
HHHHH

OUTPUT FORMAT:

* Line 1: The number of distinct districts of 7 connected cows such
        that the Jerseys outnumber the Holsteins in the district.

SAMPLE OUTPUT (file cowrig.out):

2

OUTPUT DETAILS:

The two possible districts are:
.....                .....
JHJHJ                JHJHJ
....H       and      .H...
....J                .J...
.....                .....
Any other possible district with seven cows has fewer than 4 Jerseys.

**********************************************************************

Problem 8: Feed Accounting [Hal Burch, 2004]

Farmer John is trying to figure out when his last shipment of feed
arrived.  Starting with an empty grain bin, he ordered and received
F1 (1 <= F1 <= 1,000,000) kilograms of feed.  Regrettably, he is
not certain exactly when the feed arrived. Of the F1 kilograms, F2
(1 <= F2 <= F1) kilograms of feed remain on day D (1 <= D <= 2,000).
He must determine the most recent day that his shipment could have
arrived.

Each of his C (1 <= C <= 100) cows eats exactly 1 kilogram of feed
each day. For various reasons, cows arrive on a certain day and
depart on another, so two days might have very different feed
consumption.  The input data tells which days each cow was present.
Every cow ate feed from Farmer John's bin on the day she arrived
and also on the day she left.

Given that today is day D, determine the minimum number of days
that must have passed since his last shipment.  The cows have already
eaten today, and the shipment arrived before the cows had eaten.

PROBLEM NAME: fcount

INPUT FORMAT:

* Line 1: Four space-separated integers: C, F1, F2, and D

* Lines 2..C+1: Line i+1 contains two space-separated integers
        describing the presence of a cow.  The first integer tells the
        first day the cow was on the farm; the second tells the final
        day of the cow's presence. Each day is in the range 1..2,000.

SAMPLE INPUT (file fcount.in):

3 14 4 10
1 9
5 8
8 12

INPUT DETAILS:

The shipment was 14 kilograms of feed, and Farmer John has 4 kilograms
left.  He had three cows that ate feed for some amount of time in
the last 10 days.

OUTPUT FORMAT:

The last day that the shipment might have arrived, an integer that
will always be positive.

SAMPLE OUTPUT (file fcount.out):

6

OUTPUT DETAILS:

If Farmer John started with 14 kg of feed on day 6, then on days 6
and 7, two kilograms would be eaten each day.  On day 8, three
kilograms would be eaten.  On day 9, two kilograms would be eaten.
On day 10, one kilogram would be eaten.  Thus, the total eaten would
be 2 + 2 + 3 + 2 + 1 = 10, leaving him with 4 kilograms.

**********************************************************************