1071 - At Odds:: HUST Online Judge

1071 - At Odds

Time Limit : 3 Second

Memory Limit : 128 MB

Submission: 35

Solved: 7

Description

You are in charge of N people that will be split into two teams. Each team should have the same number of people (yes, that does mean that N will be even). But there is a slight problem. People don't always get along, so it is your job to make sure that the teams you pick go well with each other. Luckily for you the requests from the team members all have the same form. Groups of three have requested that they not all be on the same team.
Now you must write a program that given a list of people and their requests divides them into two teams. If there is no possible way to form the teams such that all the requests are met, then print out "These people are impossible!" If there are multiple ways to form the teams, then have the first team be the lowest lexicographically.

Input

There will be several test cases.
Each test case will start with an even integer N. N will be at least 4 and at most 20. On the next line will be N names. Each name will contain at most ten alphabetic characters. In each name only the first character will be uppercase.
On the next line will be a positive integer M. The M requests follow. Each request will be on a line by itself and contain three names from the list above.

Output

For each case start the output with a line "Teams for test case #:" with the test case number in place of the #.
If there are no teams that respect the requests, then output "These people are impossible!"
If there are valid teams, then list all the members of the first team in alphabetical order, then list all the members of the second team in alphabetical order.
Print an empty line between test cases.

sample input

4
Anne Bob Christina Dan
1
Anne Bob Christina
6
Anne Bob Christina Dan Edward Fiona
1
Anne Bob Christina
6
Anne Bob Christina Dan Edward Fiona
4
Anne Bob Christina
Anne Bob Dan
Anne Bob Edward
Christina Dan Edward

sample output

Teams for test case 1:
Anne Bob
Christina Dan

Teams for test case 2:
Anne Bob Dan
Christina Edward Fiona

Teams for test case 3:
Anne Christina Dan
Bob Edward Fiona

hint

source