**********************************************************************
                          GOLD PROBLEMS
**********************************************************************
                 Three problems numbered 1 through 3
**********************************************************************

Problem 1: Gold Balanced Lineup [Brian Dean, 2007]

Farmer John's N cows (1 <= N <= 100,000) share many similarities.
In fact, FJ has been able to narrow down the list of features shared
by his cows to a list of only K different features (1 <= K <= 30).
For example, cows exhibiting feature #1 might have spots, cows
exhibiting feature #2 might prefer C to Pascal, and so on.

FJ has even devised a concise way to describe each cow in terms of
its "feature ID", a single K-bit integer whose binary representation
tells us the set of features exhibited by the cow. As an example,
suppose a cow has feature ID = 13. Since 13 written in binary is
1101, this means our cow exhibits features 1, 3, and 4 (reading
right to left), but not feature 2. More generally, we find a 1 in
the 2^(i-1) place if a cow exhibits feature i.

Always the sensitive fellow, FJ lined up cows 1..N in a long row
and noticed that certain ranges of cows are somewhat "balanced" in
terms of the features the exhibit. A contiguous range of cows i..j
is balanced if each of the K possible features is exhibited by the
same number of cows in the range. FJ is curious as to the size of
the largest balanced range of cows. See if you can determine it.

PROBLEM NAME: lineup

INPUT FORMAT:

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

* Lines 2..N+1: Line i+1 contains a single K-bit integer specifying
       the features present in cow i.  The least-significant bit of
       this integer is 1 if the cow exhibits feature #1, and the
       most-significant bit is 1 if the cow exhibits feature #K.

SAMPLE INPUT (file lineup.in):

7 3
7
6
7
2
1
4
2

INPUT DETAILS:

The line has 7 cows with 3 features; the table below summarizes the
correspondence:
             Feature 3:   1   1   1   0   0   1   0
             Feature 2:   1   1   1   1   0   0   1
             Feature 1:   1   0   1   0   1   0   0
             Key:         7   6   7   2   1   4   2
             Cow #:       1   2   3   4   5   6   7

OUTPUT FORMAT:

* Line 1: A single integer giving the size of the largest contiguous
       balanced group of cows.

SAMPLE OUTPUT (file lineup.out):

4

OUTPUT DETAILS:

In the range from cow #3 to cow #6 (of size 4), each feature appears
in exactly 2 cows in this range:
             Feature 3:     1   0   0   1  -> two total
             Feature 2:     1   1   0   0  -> two total
             Feature 1:     1   0   1   0  -> two total
             Key:           7   2   1   4
             Cow #:         3   4   5   6

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

Problem 2: Ranking the Cows [Richard Ho, 2006]

Each of Farmer John's N cows (1 <= N <= 1,000) produces milk at a
different positive rate, and FJ would like to order his cows according
to these rates from the fastest milk producer to the slowest.

FJ has already compared the milk output rate for M (1 <= M <= 10,000)
pairs of cows.  He wants to make a list of C additional pairs of
cows such that, if he now compares those C pairs, he will definitely
be able to deduce the correct ordering of all N cows.  Please help
him determine the minimum value of C for which such a list is
possible.

PROBLEM NAME: ranking

INPUT FORMAT:

* Line 1: Two space-separated integers: N and M

* Lines 2..M+1: Two space-separated integers, respectively: X and Y.
       Both X and Y are in the range 1...N and describe a comparison
       where cow X was ranked higher than cow Y.

SAMPLE INPUT (file ranking.in):

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

INPUT DETAILS:

FJ is comparing 5 cows and has already determined that cow 2 > cow
1, cow 1 > cow 5, cow 2 > cow 3, cow 1 > cow 4, and cow 3 > cow 4
(where the '>' notation means "produces milk more quickly").

OUTPUT FORMAT:

* Line 1: A single integer that is the minimum value of C.

SAMPLE OUTPUT (file ranking.out):

3

OUTPUT DETAILS:

From the information in the 5 test results, Farmer John knows that
since cow 2 > cow 1 > cow 5 and cow 2 > cow 3 > cow 4, cow 2 has
the highest rank. However, he needs to know whether cow 1 > cow 3
to determine the cow with the second highest rank. Also, he will
need one more question to determine the ordering between cow 4 and
cow 5. After that, he will need to know if cow 5 > cow 3 if cow 1
has higher rank than cow 3. He will have to ask three questions in
order to be sure he has the rankings: "Is cow 1 > cow 3?  Is cow 4
> cow 5? Is cow 5 > cow 3?"

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

Problem 3: Face The Right Way [Jeffrey Wang, 2007]

Farmer John has arranged his N (1 <= N <= 5,000) cows in a row and
many of them are facing forward, like good cows, Some of them are
facing backward, though, and he needs them all to face forward to
make his life perfect.

Fortunately, FJ recently bought an automatic cow turning machine.
Since he purchased the discount model, it must be irrevocably preset
to turn K (1 <= K <= N) cows at once, and it can only turn cows
that are all standing next to each other in line. Each time the
machine is used, it reverses the facing direction of a contiguous
group of K cows in the line (one cannot use it on fewer than K cows,
e.g., at the either end of the line of cows). Each cow remains in
the same *location* as before, but ends up facing the *opposite
direction*.  A cow that starts out facing forward will be turned
backward by the machine and vice-versa.

Because FJ must pick a single, never-changing value of K, please
help him determine the minimum value of K that minimizes the number of
operations required by the machine to make all the cows face forward.
Also determine M, the minimum number of machine operations required
to get all the cows facing forward using that value of K.

PROBLEM NAME: cowturn

INPUT FORMAT:

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 contains a single character, F or B,
       indicating whether cow i is facing forward or backward.

SAMPLE INPUT (file cowturn.in):

7
B
B
F
B
F
B
B

INPUT DETAILS:

There are seven cows and they are facing backward, backward, forward,
backward, forward, backward, and backward, respectively.

OUTPUT FORMAT:

* Line 1: Two space-separated integers: K and M

SAMPLE OUTPUT (file cowturn.out):

3 3

OUTPUT DETAILS:

For K = 3, the machine must be operated three times: turn cows (1,2,3),
(3,4,5), and finally (5,6,7):

     B > F   F   F
     B > F   F   F
     F > B > F   F
     B   B > F   F
     F   F > B > F
     B   B   B > F
     B   B   B > F

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