Problem D
Draft Time
The NFL draft is soon upon us and it is only a few weeks until the best college players will have their dreams come true by joining a professional (American) football team. As always your friend Bubba just won’t stop talking about it.
The NFL draft is a process where $N$ NFL teams select college players, one at a time, in $M$ rounds from a pool of $K$ total players. Bubba has checked with all his sources in the different teams and already knows how each team rates each of the college players. Knowing how the draft will end a few weeks early has left Bubba with some time to solve his favourite problem. Would it be possible be to make this draft a happy draft; a draft where all the teams and all the players are happy with the result?
Bubba thinks all teams and all players will be happy with the result if there exists no player $P$ and team $T$ such that both of the following are true:
-
$P$ is undrafted or would prefer to go to team $T$ over the team he got drafted by
-
$T$ can draft more players or would prefer $P$ over one of the players they have already drafted
Thankfully all the college players keep their SnapFace profiles up to date with a ranked list of their favourite NFL teams. Can you help Bubba create a happy draft?
Input
The first line of the input consists of three integers
$N$, $M$ and $K$ representing the number of NFL
teams, the number of rounds in this years draft, and the number
of players in the draft.
Then follows $N$ lines.
Each line begins with a word, the name of the NFL team,
followed by $K$ words, the
name of every player in the draft, rated from best to worst
according to this team.
Then follows $K$ lines.
Each line begins with a word, the name of the player, followed
by $N$ words, the name of
every NFL team in the draft, rated from best to worst according
to this player.
Output
Output the result of a happy draft if one is possible and Hello darkness my old friend! if no happy draft can be made. A happy draft should be formatted on $N$ lines. Each line begins with a word, the name of the NFL team, followed by $M$ words, the names of the players drafted by this team. Any happy draft on this format will be accepted.
Limits
-
$1 \leq N \leq 50$
-
$1 \leq M \leq 100$
-
$N\cdot M \leq K \leq 10\, 000$
-
All team names $T$ and player names $P$ are unique, and consists of between $1$ and $20$ characters in the range a–z.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 2 6 browns martellus tyrod tom john teddy danny rams danny tyrod martellus john teddy tom giants teddy danny tyrod john tom martellus teddy giants browns rams danny giants browns rams tyrod giants rams browns john giants rams browns tom browns giants rams martellus giants browns rams |
browns martellus tom rams tyrod john giants teddy danny |
