#include <assert.h>

#include <string>
#include <fstream>
#include <iostream>

#include <algorithm>
#include <vector>
#include <set>
#include <map>

#include <string.h>

struct Item {
	typedef std::set< const Item * > ConstPointerSet;
	typedef std::vector< const Item * > ConstPointerVector;
	typedef std::set< Item > Set;
	
	std::string name;
	ConstPointerSet requiredItems;

	Item( const std::string &name ) : name( name ) {
	}

	bool CanBeInserted( const ConstPointerSet &usedItems ) const {
		ConstPointerSet::const_iterator usedIter = usedItems.begin();
		ConstPointerSet::const_iterator requiredIter = requiredItems.begin();
		while( usedIter != usedItems.end() && requiredIter != requiredItems.end() ) {
			if( *usedIter < *requiredIter ) {
				usedIter++;
			} else if( *requiredIter < *usedIter ) {
				// this means that at least one item is in requiredItems that isn't in usedItems
				// => the difference can't be empty
				return false;
			} else if( *usedIter == *requiredIter ) {
				usedIter++;
				requiredIter++;
			}
		}
		// if the iteration through requiredItems has finished (without returning false), all items are in usedItems, too
		if( requiredIter == requiredItems.end() ) {
			return true;
		// else only the iteration through usedItems has finished, but the iteration through requiredItems hasn't and consequently there are still items left over
		} else {
			return false;
		}
	}
};

bool operator <( const Item &a, const Item &b ) {
	return a.name < b.name;
}

/*
Definition:
~~~~~~~~~~

[Items]
A
B 
C
...
[Rules]
A B
A C
..

*/
void ParseDefinitionFile( const char *filename, Item::Set &itemSet ) {
	
	std::ifstream file( filename );
	std::string token;

	file >> token;
	if( 0 != stricmp( token.c_str(), "[items]" ) ) {
		return;
	}
	while( file >> token, 0 != stricmp( token.c_str(), "[rules]" ) && !file.eof() ) {
		itemSet.insert( Item( token ) );
	}
	if( file.eof() ) {
		return;
	}
	bool parseRequiredItem = true;
	const Item *requiredItem;
	do {
		file >> token;
		Item *item = 0;
		for( Item::Set::iterator iter = itemSet.begin() ; iter != itemSet.end() ; iter++ ) {
			if( stricmp( iter->name.c_str(), token.c_str () ) == 0 ) {
				item = &*iter;
				break;
			}
		}
		if( item == 0 ) {
			std::cout << "Bad token '" << token << "'" << std::endl;
			break;
		}
		if( parseRequiredItem ) {
			requiredItem = item;			
		} else {
			item->requiredItems.insert( requiredItem );
		}
		
		parseRequiredItem = !parseRequiredItem;
	} while( !file.eof() );
}

struct ItemOrder {
	typedef std::vector< ItemOrder > Vector;

	Item::ConstPointerVector order;
};

struct DressingSolutions {
	const Item::Set &itemSet;
	ItemOrder::Vector solutionList;

	DressingSolutions( const Item::Set &itemSet ) : itemSet( itemSet ) {
	}

protected:
	void Solve_r( Item::ConstPointerSet &usedItems, ItemOrder &currentOrder ) {
		if( itemSet.size() == usedItems.size() ) {
			solutionList.push_back( currentOrder );
			return;
		}
		for( Item::Set::const_iterator iter = itemSet.begin() ; iter != itemSet.end() ; iter++ ) {
			if( iter->CanBeInserted( usedItems ) && usedItems.find( &*iter ) == usedItems.end() ) {
				Item::ConstPointerSet newUsedItems = usedItems;
				newUsedItems.insert( &*iter );
				ItemOrder newOrder = currentOrder;
				newOrder.order.push_back( &*iter );
				Solve_r( newUsedItems, newOrder );	
			}
		}
	}

public:
	void Solve() {
		Item::ConstPointerSet usedItems;
		ItemOrder order;
		Solve_r( usedItems, order );
	}

protected:
	void OutputSolution( const unsigned solutionIndex ) const {
		//std::cout << "Lösung #" << (solutionIndex + 1) << std::endl;
		std::cout << "Lösung #" << (solutionIndex + 1) << ": ";
		const ItemOrder &solution = solutionList[ solutionIndex ];
		for( unsigned itemIndex = 0 ; itemIndex < solution.order.size() ; itemIndex++ ) {
			const Item &item = *solution.order[ itemIndex ];
			//std::cout << (itemIndex + 1) << ". " << item.name << std::endl;
			if( itemIndex != 0 ) {
				std::cout << "->";
			}
			std::cout << item.name;
		}
		std::cout << std::endl;
	}

public:
	void OutputFirstSolution() const {
		if( !solutionList.empty() ) {
			OutputSolution( 0 );
		}
	}

	void OutputSolutions() const {
		std::cout << solutionList.size() << " Lösungen gefunden" << std::endl << std::endl;
		for( unsigned solutionIndex = 0 ; solutionIndex < solutionList.size() ; solutionIndex++ ) {
			OutputSolution( solutionIndex );
		}
	}
};

int main( int argc, char *argv[] ) {
	if( argc < 2 ) {
		return -1;
	}
	bool allSolutions = true;
	if( argc == 3 ) {
		if( stricmp( argv[ 2 ], "single" ) == 0 ) {
			allSolutions = false;
		}
	}
	Item::Set itemSet;
	ParseDefinitionFile( argv[1], itemSet );

	DressingSolutions dressing( itemSet );
	dressing.Solve();
	if( allSolutions ) {
		dressing.OutputSolutions();
	} else {
		dressing.OutputFirstSolution();
	}

	return 0;
}