시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB0000.000%

문제

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 c 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

입력

The first line contains three integers n, k, and c (1 ≤ n ≤ 17, 0 ≤ k ≤ n(n−1)/2 and 1 ≤ c ≤ n) – the number of kids, pairs of enemies, and the capacity of the bus, respectively. Then follow n lines with the kids’ names. Each name consists solely of the characters A-Z and a-z, is non-empty, and at most 10 characters long. Then follow k 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.

출력

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).

예제 입력 1

2 0 1
Alice
Bob

예제 출력 1

2
Alice
Bob

예제 입력 2

3 2 3
Alice
Charlie
Bob
Alice Charlie
Bob Charlie

예제 출력 2

2
Alice Bob
Charlie

출처

Contest > KTH Challenge > KTH Challenge 2018 A번

  • 문제를 만든 사람: Johan Sannemo