Help the Leaders

Have you ever listened to the speeches of leaders (Political or non-political)? People often find these speeches monotonous and hopeless. The leaders also sometimes feel very embarrassed about their speeches and they are often afraid of covering the same topics in two different speeches. You can save our intelligent leaders from these kinds of embarrassments. For example, let's consider that a leader has the following topics in his mind

a)

War

b)

Terror

c)

Peace

d)

Nuclear-Bomb

e)

Human-Right

f)

Food

g)

Oil-Crisis

h)

Equal-Right

He delivers speeches on any two of these topics at once but never wants to cover the topics ``Oil- Crisis" and ``War" in the same speech. The same thing applies for the topics ``Nuclear-Bomb" and ``Equal-Right". You can help him by making all possible combinations of topics (Of course considering the restrictions supplied by him) so that he can choose any one from them according to his convenience and can avoid any blunders. The specific details are given in the input and output specifications.

Input 

The first line of the input file contains an integer n(n100), which indicates how many sets of inputs are there. The description of each set is given in the paragraph below:

The first line of each set has three integers t( 0 < t < 16), p( 0p < t(t - 1)/2), s( 0 < s5). Here t denotes the number of topics in the leader's mind, p denotes the number of prohibited pairs and s is the total number of topics the leader wants to cover in a single speech. The next t lines contain t topics of the leader's mind. The topics are all different. Each topic will contain only alphanumeric characters and hyphens. Each of the next p lines contains two different topics in each line separated by a single space. These pairs of topics should not come in the same speech. Same pair of topics may appear more than once in the input. Each topic has a maximum length of 15.

Output 

For each set you should first print the serial of that set. Each of the next lines should contain all the possible topic groups. The topics in each group should be separated by a single space. Print a blank line after the output for each set of input. In a group the topics should be printed in the descending order of their lengths. If lengths of two topics are same the lexicographically smaller one should come first. This order should also be maintained in the printing order of the groups.

Topics should be considered case insensitive. While printing the topics print all the characters as uppercase. Print a blank line after the output for each case.

Sample Input 

2
8 2 2
WAR
TERROR
PEACE
NUCLEAR-BOMB
HUMAN-RIGHT
FOOD
OIL-CRISIS
EQUAL-RIGHT
WAR OIL-CRISIS
EQUAL-RIGHT NUCLEAR-BOMB
8 0 1
WAR
TERROR
PEACE
NUCLEAR-BOMB
HUMAN-RIGHT
FOOD
OIL-CRISIS
EQUAL-RIGHT

Output for Sample Input 

Set 1:
NUCLEAR-BOMB HUMAN-RIGHT
NUCLEAR-BOMB OIL-CRISIS
NUCLEAR-BOMB TERROR
NUCLEAR-BOMB PEACE
NUCLEAR-BOMB FOOD
NUCLEAR-BOMB WAR
EQUAL-RIGHT HUMAN-RIGHT
EQUAL-RIGHT OIL-CRISIS
EQUAL-RIGHT TERROR
EQUAL-RIGHT PEACE
EQUAL-RIGHT FOOD
EQUAL-RIGHT WAR
HUMAN-RIGHT OIL-CRISIS
HUMAN-RIGHT TERROR
HUMAN-RIGHT PEACE
HUMAN-RIGHT FOOD
HUMAN-RIGHT WAR
OIL-CRISIS TERROR
OIL-CRISIS PEACE
OIL-CRISIS FOOD
TERROR PEACE
TERROR FOOD
TERROR WAR
PEACE FOOD
PEACE WAR
FOOD WAR

Set 2:
NUCLEAR-BOMB
EQUAL-RIGHT
HUMAN-RIGHT
OIL-CRISIS
TERROR
PEACE
FOOD
WAR

---

Problem-setter: Shahriar Manzoor, ACM Valladolid Online Judge


題目給定演講標題，有些標題不會同時講，而每次要演講的題目指定個數，
生成所有可能的組合方式。必須按照字典順序輸出，在窮舉前先進行排序。

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
int n, cond, m, g[20][20];
string topic[20];
int ch[20];
void dfs(int idx, int i) {
    if(idx == m) {
        for(i = 0; i < idx; i++) {
            if(i)   putchar(' ');
            printf("%s", topic[ch[i]].c_str());
        }
        puts("");
        return ;
    }
    int j;
    for(; i < n; i++) {
        for(j = 0; j < idx; j++)
            if(g[i][ch[j]] == 1)
                break;
        if(j == idx) {
            ch[idx] = i;
            dfs(idx+1, i+1);
        }
    }
}
bool cmp(string a, string b) {
    if(a.length() != b.length())
        return a.length() > b.length();
    return a < b;
}
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d %d", &n, &cond, &m);
        memset(g, 0, sizeof(g));
        int i, j, k;
        for(i = 0; i < n; i++) {
            cin >> topic[i];
            for(j = 0; j < topic[i].length(); j++) {
                if(topic[i][j] >= 'a' && topic[i][j] <= 'z')
                    topic[i][j] -= 32;
            }
        }
        sort(topic, topic+n, cmp);
        map<string, int> R;
        for(i = 0; i < n; i++)
            R[topic[i]] = i;
        while(cond--) {
            string tx, ty;
            cin >> tx >> ty;
            for(i = 0; i < tx.length(); i++) {
                if(tx[i] >= 'a' && tx[i] <= 'z')
                    tx[i] -= 32;
            }
            for(i = 0; i < ty.length(); i++) {
                if(ty[i] >= 'a' && ty[i] <= 'z')
                    ty[i] -= 32;
            }
            int x = R[tx], y = R[ty];
            g[x][y] = g[y][x] = 1;
        }
        printf("Set %d:\n", ++cases);
        dfs(0, 0);
        puts("");
    }
    return 0;
}