버스 계획

어느 초등학교 반이 버스를 타고 컴퓨터 공장으로 현장 학습을 가려고 한다. 그런데 운전기사는 하루 종일 싸우는 아이들을 태우고 운전하는 일에 몹시 지쳐서, 반을 여러 조로 나누어 공장으로 가자고 제안했다. 운전기사는 이미 어떤 아이들이 서로 싫어하고 싸울 것 같은지 파악했고, 그런 아이들이 같은 조에 들어가지 않게 하려고 한다. 물론 아이들을 한 명씩 따로 태워 가는 것은 시간과 돈의 낭비이므로, 운전기사는 자신이 태워 가야 할 조의 수를 최소로 줄이고 싶다. 게다가 버스가 꽤 작아서 한 번에 최대 c명까지만 탈 수 있다.

이 조 편성을 돕는 프로그램을 작성하라. 아이들의 수와 서로 싫어하는 쌍이 주어졌을 때, 필요한 조의 최소 수와 반을 그 최소 수의 조로 나누는 방법을 구하라.

첫째 줄에 세 정수 n, k, c (1 ≤ n ≤ 17, 0 ≤ k ≤ n(n−1)/2, 1 ≤ c ≤ n)가 주어진다. 각각 아이들의 수, 서로 싫어하는 쌍의 수, 버스의 정원이다. 이어서 n개의 줄에 아이들의 이름이 주어진다. 각 이름은 A-Z와 a-z 문자로만 이루어져 있고, 비어 있지 않으며 길이가 최대 10이다. 이어서 k개의 줄에 각각 공백으로 구분된 두 이름이 주어지며, 두 아이가 서로 싫어한다는 뜻이다. 같은 이름 쌍은 두 번 나타나지 않고, 자기 자신을 싫어하는 아이는 없다.

첫째 줄에 조의 최소 수를 출력하고, 이어서 각 조마다 한 줄에 그 조에 속한 아이들의 이름을 공백으로 구분해 출력한다.