/* Tyler R. Richard

   10/21/10

   This program uses sets to determine all the candidate keys and

   all non trivial closures of a given a list of

   single letter attributes and a set of functional dependences.

TODO:

-make it find canonical covers

  */

#include <iostream>

#include <cmath>

#include <algorithm>

#include <vector>

#include <string>

#include <map>

#include <set>

using namespace std;

set<char> setize(string data) {

	set<char> retval;

	for(int i = 0; i < data.size(); i++) {

		retval.insert(data[i]);

	}

	return retval;

}

int comp(set<char> a, set<char> b) {

	if(a.size() == b.size()) {

		return(a < b);

	}else{

		return(a.size() < b.size());

	}

}

string printSet(set<char> data) {

	string retval;

	for(set<char>::iterator p = data.begin(); p != data.end(); p++) {

	     retval += *p;

	}

	return(retval);

}

int main() {

	set<char> full_set;

	string determinant, product;

	map<set<char>,set<char> > F;

	map<set<char>,set<char> >::iterator it;

	cin >> determinant;

	full_set = setize(determinant);

	int n;

	cin >> n;

	// read in the functionality det pairs in

	for(int i =0; i < n; i++) {

		cin >> determinant >> product >> product;

		set<char> dets = setize(determinant);

		set<char> prods = setize(product);

		F[dets].insert(prods.begin(), prods.end());

	}

	// create a list of possible inputs

	unsigned int bitmask = 0;

	vector<char> v;

	vector<set<char> > possible_keys;

	for(set<char>::iterator i = full_set.begin(); i != full_set.end(); i++) {

		v.push_back(*i);

	}

	// assume # of attributes < 32

	while(bitmask <= 1<<v.size()){

		bitmask++;

		unsigned int index = 1;

		set<char> dets;

		for(int i = 0; i < v.size(); i++ ) {

			if(index & bitmask) {

				dets.insert(v[i]);

			}

			index = index << 1;

		}

		possible_keys.push_back(dets);

	}

	sort(possible_keys.begin(), possible_keys.end(),comp);

	vector<set<char> > found_keys;

	for(int i = 0; i < possible_keys.size(); i++) {

		//cout << printSet(possible_keys[i]);

		set<char> dets = possible_keys[i];

		bool cont = true;

		for(int j =0 ; j < found_keys.size(); j++) {

			if(includes( 

					dets.begin(), dets.end(),

					found_keys[j].begin(), found_keys[j].end())

			  ){

				//this key is a super set of a key we've already discovered

				cont = false;

				break;

			}

		}

		if(!cont){

			continue;

		}

		bool changes = true;

		while(changes && dets.size() != full_set.size()) {

			changes = false;

			for(it = F.begin();it != F.end() && dets.size() != full_set.size()

					; it++) {

				if(includes(dets.begin(), dets.end(),

						it->first.begin(),it->first.end()) &&

						!includes(dets.begin(), dets.end(),

							it->second.begin(), it->second.end())){

//					cout << it->first.size() << " " << dets.size() << endl;

					dets.insert(it->second.begin(),it->second.end());

					changes = true;

				}

			}

		}

		/* Print the keys that the given det can get to

		for(set<char>::iterator p=dets.begin(); p != dets.end(); p++) {

			cout << *p;

		}

		*/

		cout << printSet(possible_keys[i]);

		cout << " = ";

		cout << printSet(dets);

		if(dets.size() == full_set.size()) {

			found_keys.push_back(possible_keys[i]);

			cout << " is a candidate key!";

		}

		cout << endl;

	}	

}