Hide

Problem D
Draft Time

/problems/drafttime/file/statement/en/img-0001.jpg

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

Please log in to submit a solution to this problem

Log in