> 这题目我用回溯法AC了，WA了五六次，靠！

/*
题意：房间里N个通了电的插座，有M种电器，每种电器只有插在对应类型的插座上才能正常工作。现在有K个转换器，能将一种类型的插座转换成另一种类型的插座。
利用这K个转换器和N个通电插座，使尽量多的电器能够正常通电工作（题目要求输出最少能使多少台电器不工作的数目）。
*/

#include <iostream>
#include <fstream>
#include <string>
#include <cstdio>
#include <map>
using namespace std;

struct Plug // 电器上的插头类型
{
	int recep; // 插头需要的插座类型
	bool* list; // 使用适配器后可以匹配的插座类型
};

struct Adapter // 适配器类型
{
	int recep; // 插座类型
	int plug; // 插头类型
};

class POJ1087
{
protected:
	int numReceps; // 插座的数量
	int numPlugs; // 电器上的插头的数量
	int numAdapts; // 适配器数量
	Plug* plugs; // 电器的插座数组
	Adapter* adapts; // 适配器数组
	bool* canUse; // 某个插座能否使用
	int* matchPlug; // matchPlug[i]表示最终与电器插头i匹配的插座编号
	int* matchRecep; // matchRecep[i]表示最终插在插座i上的电器插头的编号
	map<int, string> mapId2Name;
	map<string, int> mapName2Id;
	void Init(); // 初始化
	void UseAdapter(int i); // 插头i使用适配器后，可以匹配的插座类型
	bool Backtrack(int node); // 针对电器插头node进行搜索
public:
	POJ1087();
	~POJ1087();
	void InputAndAlloc(int numReceps); // 输入某个测试用例的插座名称、插头名称、适配器名称信息
	int Solve();
};

POJ1087::POJ1087()
{
	this->numAdapts = 0;
	this->numReceps = 0;
	this->numPlugs = 0;
	plugs = NULL;
	adapts = NULL;
	canUse = NULL;
	matchPlug = NULL;
	matchRecep = NULL;
}
POJ1087::~POJ1087()
{
	for (int i = 0; i < numPlugs; i++)
	{
		delete[] plugs[i].list;
	}
	delete[] plugs;
	delete[] adapts;
	delete[] canUse;
	delete[] matchPlug;
	delete[] matchRecep;
}

// 电器插头i使用适配器后，可以匹配的插座类型。这个方法值得回味
void POJ1087::UseAdapter(int i)
{
	// 电器插头i本身与自身所需要的插座肯定匹配
	plugs[i].list[plugs[i].recep] = true;
	// 由于适配器可以插入其他的适配器，所以使用一个适配器后，又重新搜索
	bool flag = false;
	do
	{
		flag = false;
		// 遍历所有的适配器
		for (int j = 0; j < numAdapts; j++)
		{
			// 如果电器插头i通过连接某些适配器后，能匹配适配器j的插座，并且电器插头i与适配器j的插头还没建立转换关系
			if (plugs[i].list[adapts[j].recep] && !plugs[i].list[adapts[j].plug])
			{
				flag = true;
				plugs[i].list[adapts[j].plug] = true; // 将电器插头i与适配器j的插头建立转换关系
			}
		}
	} while (flag); // 只要为电器插头i找到了一个适配器，还需要重新搜索，直到为电器插头i找到所有
}

// 针对电器插头node进行搜索
bool POJ1087::Backtrack(int node)
{
	// 遍历所有的插座
	for (int j = 0; j < numReceps; j++)
	{
		// 如果电器插头node与插座可以匹配（可以通过适配器），而且插座j可用
		if (plugs[node].list[j] && canUse[j])
		{
			if (matchRecep[j] == -1) // 如果电器插头node与插座j尚未匹配
			{
				// 建立电器插头node与插座j的匹配关系
				matchRecep[j] = node;
				matchPlug[node] = j;
				return true;
			}
			else
			{
				// 将插座j原先的匹配的电器插头存放在save中
				int save = matchRecep[j];
				// 将插座j原先的匹配的插头换成node尝试一下，并取消电器插头save所匹配的插座
				matchRecep[j] = node;
				matchPlug[node] = j;
				matchPlug[save] = -1;
				// 设置插座j已经使用
				canUse[j] = false;
				// 递归递归，
				if (Backtrack(save))
				{
					return true;
				}
				// 恢复回溯前的状态
				canUse[j] = true;
				matchPlug[save] = j;
				matchPlug[node] = -1;
				matchRecep[j] = save;
			}
		}
	}
	return false;
}

// 输入某个测试用例的插座名称、插头名称、适配器名称信息
void POJ1087::InputAndAlloc(int numReceps)
{
	mapId2Name.clear();
	mapName2Id.clear();
	this->numReceps = numReceps; // 插座数量
	matchRecep = new int[numReceps];
	// 读取插座的名称，建立名称数组
	for (int i = 0; i < numReceps; i++)
	{
		string name = "";
		cin >> name;
		mapId2Name[i] = name;
		mapName2Id[name] = i;
	}

	cin >> numPlugs;
	canUse = new bool[numReceps];
	matchPlug = new int[numPlugs];
	plugs = new Plug[numPlugs];

	// 读取电器插头的名称，建立插头数组，电器的名称其实没有用
	for (int i = 0; i < numPlugs; i++)
	{
		string name = "";
		cin >> name >> name;
		if (mapName2Id.find(name) == mapName2Id.end())
		{
			mapName2Id[name] = mapName2Id.size();
			mapId2Name[mapId2Name.size()] = name;

		}
		plugs[i].recep = mapName2Id[name];
	}

	cin >> numAdapts;
	adapts = new Adapter[numAdapts];

	// 读取适配器名称，创建适配器数组
	for (int i = 0; i < numAdapts; i++)
	{
		string name = "";
		cin >> name;
		if (mapName2Id.find(name) == mapName2Id.end())
		{
			mapName2Id[name] = mapName2Id.size();
			mapId2Name[mapId2Name.size()] = name;

		}
		adapts[i].recep = mapName2Id[name];
		cin >> name;
		if (mapName2Id.find(name) == mapName2Id.end())
		{
			mapName2Id[name] = mapName2Id.size();
			mapId2Name[mapId2Name.size()] = name;

		}
		adapts[i].plug = mapName2Id[name];

		for (int i = 0; i < numPlugs; i++)
		{
			plugs[i].list = new bool[mapId2Name.size()]; 
		}
	}
}

void POJ1087::Init()
{
	for (int i = 0; i < numPlugs; i++)
	{
		for (int j = 0; j < mapId2Name.size(); j++) 
		{
			plugs[i].list[j] = false;
		}
		matchPlug[i] = -1;
	}
	for (int i = 0; i < numReceps; i++)
	{
		matchRecep[i] = -1;
		canUse[i] = true;
	}
}

int POJ1087::Solve()
{
	Init(); // 初始化
	// 遍历所有的电器插头
	for (int i = 0; i < numPlugs; i++)
	{
		// 计算电器插头i使用适配器后，可以匹配的插座类型
		UseAdapter(i);
	}
	int i = 0;
	while (i < numPlugs) // 如果还没遍历完所有的电器插头
	{
		// 遍历所有的插座
		for (int j = 0; j < numReceps; j++)
		{
			canUse[j] = true; // 设置插座j已经被占用
			// 如果插头i还没有匹配的插座
			if (matchPlug[i] == -1 && Backtrack(i))
			{
				i = 0;
			}
			else
			{
				i++;
			}
		}
	}
	// 统计哪些电器插头没有匹配的插座
	int min = 0;
	for (int i = 0; i < numPlugs; i++)
	{
		if (matchPlug[i] == -1)
		{
			min++;
		}
	}
	return min;
}

int main()
{
	int numReceps = 0;
	while (cin >> numReceps)
	{
		POJ1087 obj;
		obj.InputAndAlloc(numReceps);
		cout << obj.Solve() << "\n";
	}
	return 0;
}