Picture by AutoPhoto via Wikimedia Commons, cc by
An elementary school class is going on a road trip by bus
to a computer factory. However, the driver is really tired of
having to drive fighting kids all day, so she suggested that
the class should split up and go to the factory in groups. She
has already observed which kids dislike each other and are
likely to fight, so she wants to make sure they do not end up
in the same group. Of course, driving everyone one-by-one is a
waste of time and money, so the driver wants to minimize the
number of groups she has to drive. In addition, the bus is
pretty small, and may only fit up to
kids at a time.
You are to write a program which helps her with the task of
making these groups. Given the number of kids and their
enemies, find the minimum number of groups required, as well as
a division of the class into this minimum number of groups
Input
The first line contains three integers , , and (, and ) – the number of kids,
pairs of enemies, and the capacity of the bus, respectively.
Then follow lines with
the kids’ names. Each name consists solely of the characters
A-Z and a-z, is non-empty, and at most characters long. Then follow
lines, each containing
a pair of space-separated names indicating a pair of kids that
dislike each other. No pair of names appears twice, and no kid
is their own enemy.
Output
On the first line, output the minimum number of groups,
followed by one line per group containing the names of the
children in that group (separated by spaces).
| Sample Input 1 |
Sample Output 1 |
2 0 1
Alice
Bob
|
2
Alice
Bob
|
| Sample Input 2 |
Sample Output 2 |
3 2 3
Alice
Charlie
Bob
Alice Charlie
Bob Charlie
|
2
Alice Bob
Charlie
|
