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

Problem 6: Cleaning Shifts [USACO Coaches, 2004]

Farmer John is assigning some of his N (1 <= N <= 25,000) cows to
do some cleaning chores around the barn.  He always wants to have
one cow working on cleaning things up and has divided the day into
T shifts (1 <= T <= 1,000,000), the first being shift 1 and the
last being shift T.

Each cow is only available at some interval of times during the day
for work on cleaning. Any cow that is selected for cleaning duty
will work for the entirety of her interval.

Your job is to help Farmer John assign some cows to shifts so that
(i) every shift has at least one cow assigned to it, and (ii) as
few cows as possible are involved in cleaning. If it is not possible
to assign a cow to each shift, print -1.

PROBLEM NAME: cleaning

INPUT FORMAT:

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

* Lines 2..N+1: Each line contains the start and end times of the
        interval during which a cow can work.  A cow starts work at
        the start time and finishes after the end time.

SAMPLE INPUT (file cleaning.in):

3 10
1 7
3 6
6 10

INPUT DETAILS:

There are 3 cows and 10 shifts.  Cow #1 can work shifts 1..7, cow #2 can
work shifts 3..6, and cow #3 can work shifts 6..10.

OUTPUT FORMAT:

* Line 1: The minimum number of cows Farmer John needs to hire or -1
        if it is not  possible to assign a cow to each shift.

SAMPLE OUTPUT (file cleaning.out):

2

OUTPUT DETAILS:

By selecting cows #1 and #3, all shifts are covered.  There is no way to
cover all the shifts using fewer than 2 cows.

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

Problem 7: Bad Cowtractors [Tim Abbott, 2004]

Bessie has been hired to build a cheap internet network among Farmer
John's N (2 <= N <= 1,000) barns that are conveniently numbered
1..N. FJ has already done some surveying, and found M (1 <= M <=
20,000) possible connection routes between pairs of barns.  Each
possible connection route has an associated cost C (1 <= C <=
100,000).  Farmer John wants to spend the least amount on connecting
the network; he doesn't even want to pay Bessie.

Realizing Farmer John will not pay her, Bessie decides to do the
worst job possible.  She must decide on a set of connections to
install so that (i) the total cost of these connections is as large
as possible, (ii) all the barns are connected together (so that it
is possible to reach any barn from any other barn via a path of
installed connections), and (iii) so that there are no cycles among
the connections (which Farmer John would easily be able to detect).
Conditions (ii) and (iii) ensure that the final set of connections
will look like a "tree".

PROBLEM NAME: cowtract

INPUT FORMAT:

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

* Lines 2..M+1: Each line contains three space-separated integers A,
        B, and C that describe a connection route between barns A and
        B of cost C.

SAMPLE INPUT (file cowtract.in):

5 8
1 2 3
1 3 7
2 3 10
2 4 4
2 5 8
3 4 6
3 5 2
4 5 17

OUTPUT FORMAT:

* Line 1: A single integer, containing the price of the most expensive
        tree connecting all the barns.  If it is not possible to
        connect all the barns, output -1.

SAMPLE OUTPUT (file cowtract.out):

42

OUTPUT DETAILS:

The most expensive tree has cost 17 + 8 + 10 + 7 = 42.  It uses the following 
connections: 4 to 5, 2 to 5, 2 to 3, and 1 to 3.

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

Problem 8: Tree Cutting [Hal Burch, 2004]

After Farmer John realized that Bessie had installed a "tree-shaped"
network among his N (1 <= N <= 10,000) barns at an incredible cost,
he sued Bessie to mitigate his losses.

Bessie, feeling vindictive, decided to sabotage Farmer John's network
by cutting power to one of the barns (thereby disrupting all the
connections involving that barn).  When Bessie does this, it breaks
the network into smaller pieces, each of which retains full
connectivity within itself.  In order to be as disruptive as possible,
Bessie wants to make sure that each of these pieces connects together
no more than half the barns on FJ.

Please help Bessie determine all of the barns that would be suitable
to disconnect.

PROBLEM NAME: treecut

INPUT FORMAT:

* Line 1: A single integer, N.  The barns are numbered 1..N.

* Lines 2..N: Each line contains two integers X and Y and represents a
        connection between barns X and Y.

SAMPLE INPUT (file treecut.in):

10
1 2
2 3
3 4
4 5
6 7
7 8
8 9
9 10
3 8

INPUT DETAILS:

The set of connections in the input describes a "tree": it connects all the
barns together and contains no cycles.

OUTPUT FORMAT:

* Lines 1..?: Each line contains a single integer, the number (from
        1..N) of a barn whose removal splits the network into pieces
        each having at most half the original number of barns.  Output
        the barns in increasing numerical order.  If there are no
        suitable barns, the output should be a single line containing
        the word "NONE".

SAMPLE OUTPUT (file treecut.out):

3
8

OUTPUT DETAILS:

If barn 3 or barn 8 is removed, then the remaining network will have one
piece consisting of 5 barns and two pieces containing 2 barns.  If any
other barn is removed then at least one of the remaining pieces has size at
least 6 (which is more than half of the original number of barns, 5).

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