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