// https://pydefis.callicode.fr/defis/TroisTables/txt
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <utility>
#include <cstdlib>
using namespace std;

const vector<string> convives =
{"ANNE", "BERNARD", "CELINE", "CHRISTINE", "CHRISTOPHE", "DANIEL", "ERIC", "FREDERIC", "JEANNE",
	"JULIEN", "LAURENT", "MARIE", "MARTINE", "MICHEL", "MONIQUE", "NATHALIE", "NICOLAS",
	"NICOLE", "PASCAL", "PATRICK", "PHILIPPE", "PIERRE", "SANDRINE", "SEBASTIEN", "SOPHIE",
	"STEPHANE", "STEPHANIE", "SYLVIE", "VALERIE", "VERONIQUE"};

const set<pair<string, string>> incompatibles =
{{"ANNE", "PHILIPPE"}, {"VALERIE", "ANNE"}, {"ANNE", "VERONIQUE"}, {"MARTINE", "BERNARD"},
	{"SANDRINE", "CELINE"}, {"SEBASTIEN", "CELINE"}, {"VALERIE", "CELINE"},
	{"CHRISTINE", "DANIEL"}, {"CHRISTINE", "JULIEN"}, {"LAURENT", "CHRISTINE"},
	{"MICHEL", "CHRISTINE"}, {"CHRISTINE", "NATHALIE"}, {"CHRISTINE", "SEBASTIEN"},
	{"STEPHANE", "CHRISTINE"}, {"CHRISTINE", "SYLVIE"}, {"CELINE", "CHRISTOPHE"},
	{"DANIEL", "CHRISTOPHE"}, {"NICOLE", "CHRISTOPHE"}, {"PHILIPPE", "CHRISTOPHE"},
	{"SEBASTIEN", "CHRISTOPHE"}, {"CHRISTOPHE", "STEPHANE"}, {"CHRISTOPHE", "SYLVIE"},
	{"VALERIE", "CHRISTOPHE"}, {"ERIC", "LAURENT"}, {"ERIC", "MARTINE"}, {"ERIC", "PHILIPPE"},
	{"ERIC", "VALERIE"}, {"ERIC", "VERONIQUE"}, {"ANNE", "FREDERIC"}, {"FREDERIC", "BERNARD"},
	{"CELINE", "FREDERIC"}, {"FREDERIC", "JULIEN"}, {"FREDERIC", "LAURENT"},
	{"FREDERIC", "SANDRINE"}, {"STEPHANE", "FREDERIC"}, {"BERNARD", "JEANNE"},
	{"JEANNE", "DANIEL"}, {"JULIEN", "JEANNE"}, {"LAURENT", "JEANNE"}, {"JEANNE", "MONIQUE"},
	{"JEANNE", "SANDRINE"}, {"JEANNE", "SEBASTIEN"}, {"JULIEN", "MARTINE"},
	{"NATHALIE", "JULIEN"}, {"CELINE", "MARIE"}, {"ERIC", "MARIE"}, {"MARIE", "JULIEN"},
	{"MARIE", "MONIQUE"}, {"NATHALIE", "MARIE"}, {"SEBASTIEN", "MARIE"}, {"MARIE", "STEPHANE"},
	{"SYLVIE", "MARIE"}, {"DANIEL", "MICHEL"}, {"MICHEL", "PHILIPPE"}, {"SANDRINE", "MICHEL"},
	{"VALERIE", "MICHEL"}, {"VERONIQUE", "MICHEL"}, {"PHILIPPE", "NICOLAS"},
	{"NICOLAS", "SEBASTIEN"}, {"NICOLAS", "VALERIE"}, {"NICOLE", "DANIEL"},
	{"NICOLE", "LAURENT"}, {"MONIQUE", "NICOLE"}, {"NICOLE", "NATHALIE"},
	{"PHILIPPE", "NICOLE"}, {"SANDRINE", "NICOLE"}, {"NICOLE", "SEBASTIEN"},
	{"NICOLE", "VALERIE"}, {"PASCAL", "DANIEL"}, {"PASCAL", "JULIEN"}, {"PASCAL", "MICHEL"},
	{"PASCAL", "NATHALIE"}, {"PASCAL", "SANDRINE"}, {"PASCAL", "SEBASTIEN"},
	{"SYLVIE", "PASCAL"}, {"PATRICK", "ANNE"}, {"PATRICK", "CELINE"}, {"PATRICK", "JULIEN"},
	{"MARTINE", "PATRICK"}, {"PATRICK", "NICOLAS"}, {"NICOLE", "PATRICK"},
	{"SEBASTIEN", "PATRICK"}, {"PATRICK", "STEPHANE"}, {"PIERRE", "CELINE"},
	{"PIERRE", "DANIEL"}, {"PIERRE", "LAURENT"}, {"PIERRE", "MONIQUE"},
	{"PIERRE", "NATHALIE"}, {"SYLVIE", "PIERRE"}, {"VALERIE", "PIERRE"}, {"SOPHIE", "DANIEL"},
	{"MARTINE", "SOPHIE"}, {"SOPHIE", "SEBASTIEN"}, {"SOPHIE", "STEPHANE"},
	{"SANDRINE", "STEPHANE"}, {"STEPHANIE", "BERNARD"}, {"STEPHANIE", "LAURENT"},
	{"MARTINE", "SYLVIE"}, {"SEBASTIEN", "SYLVIE"}, {"SYLVIE", "VALERIE"}};

const int C = 30;	// nombre de convives
const int T = 3;	// nombre de tables
const int P = 10;	// nombre de personnes à chaque table

map<string, set<string>> inco; // personnes incompatibles
map<string, int> aTable; // assignation des tables

// Est-ce qu'on peut placer la personne k à la table c ?
bool isSafe(int k, int c)
{
	for(auto &inc : inco[convives[k]]) // personnes NON compatibles avec k
		if(aTable[inc] == c) // une personne incompatible avec k est déjà à la table c
			return false;
 
	return true;
} //isSafe()

// https://www.geeksforgeeks.org/graph-coloring-applications/
bool graphColoringUtil(int m, int k)
{
	// Base case: if all vertices are assigned a color, then return true
	if(k == C)
	{
		// Reste à vérifier s'il y a bien P personnes par table
		vector<int> combien(T, 0);
		for(auto &paire : aTable)
			combien[paire.second - 1]++;

		for(auto &x : combien)
			if(x != P)
				return false;

		return true;
	}
	 
	// Consider person k and try different colors
	for(int c = 1; c <= m; c++)
	{
		// Check if assignment of color c to v is fine
		if(isSafe(k, c))
		{
			aTable[convives[k]] = c;
	 
			// Recur to assign colors to rest of the vertices
			if(graphColoringUtil(m, k + 1) == true)
				return true;
	 
			// if assigning color c doesn't lead to a solution, then remove it
			aTable[convives[k]] = 0;
		}
	}
	 
	// If no color can be assigned to this vertex, then return false
	return false;
} // graphColoringUtil()

// Graph coloring with fixed number of colors
bool graphColoring(int m)
{
	// Initialize all color values as 0.
	// This initialization is needed for correct functioning of isSafe()
	for(auto &pers : convives)
		aTable[pers] = 0;
	 
	// Call graphColoringUtil() for vertex 0
	if(graphColoringUtil(m, 0) == false)
	{
		cout << "Aucune solution !\n";
		return false;
	}
	 
	// Print the solution
	/*for(auto &pers: convives)
		cout << pers << " : table #" << aTable[pers] << '\n';
	cout << '\n';*/

	return true;
} // graphColoring()

int main()
{
	for(auto &pers : convives)
	{
		for(auto &paire : incompatibles)
		{
			if(paire.first == pers)
			{
				inco[pers].insert(paire.second);
			}
			else if(paire.second == pers)
			{
				inco[pers].insert(paire.first);
			}
		}
	}

	/*cout << "INCOMPATIBLES : \n";
	for(auto &elt: inco)
	{
		cout << elt.first << " : ";
		for(auto &p: elt.second)
			cout << p << ", ";
		cout << "\b\b \n\n";
	}*/


	if(graphColoring(T))
	{
		for(int t = 1; t <= 3; t++)
		{
			cout << "TABLE #" << t << " : ";
			for(auto &elt : aTable)
				if(elt.second == t)
					cout << elt.first << ", ";
			cout << "\b\b \n";
		}
	}

	return 0;
} // main()