// 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)
{
	// À COMPLÉTER
 
	return true;
} //isSafe()

// https://www.geeksforgeeks.org/graph-coloring-applications/
bool graphColoringUtil(int m, int k)
{
	// À COMPLÉTER

	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;
	}
	 
	return true;
} // graphColoring()

int main()
{
	// Construction du graphe (liste d'adjacences)
	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);
			}
		}
	}

	if(graphColoring(T))
	{
		// Afficher les noms des personnes à chaque table
	}
	else
	{
		cout << "Aucune solution\n";
	}

	return 0;
} // main()